문제 풀이 [luoguP 4145 하나님 이 문 제 를 만 드 신 7 분 2 (화신 이 각국 을 돌아 다 니 며)]

#include 
#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 100100;

int n, m;
int cnt;
LL a[MAXN];
struct node
{
    int left, right;
    LL s, Max;
    node *ch[2];
}pool[MAXN << 2], *root;

inline void pushup(node *r)
{
    r->s = r->ch[0]->s + r->ch[1]->s;
    r->Max = max(r->ch[0]->Max, r->ch[1]->Max);
}

inline void Build_Tree(node *r, int left, int right)
{
    r->left = left;
    r->right = right;
    if(left == right)
    {
        r->s = r->Max = a[left];
        return ;
    }
    int mid = (left + right) / 2;
    node *lson = &pool[++cnt];
    node *rson = &pool[++cnt];
    r->ch[0] = lson;
    r->ch[1] = rson;
    Build_Tree(lson, left, mid);
    Build_Tree(rson, mid + 1, right);
    pushup(r);
}

inline void change(node *r, int left, int right)
{
    if(r->left == r->right)
    {
        r->s = sqrt(r->s);
        r->Max = sqrt(r->Max);
        return ;
    }

    int mid = (r->left +r-> right) / 2;
    if(left <= mid && r->ch[0]->Max > 1) change(r->ch[0], left, right);
    if(mid < right && r->ch[1]->Max > 1) change(r->ch[1], left, right);
    pushup(r);
}

inline LL query(node *r, int left, int right)
{
    if(r->left == left && r->right == right)
        return r->s;
    if(r->ch[0]->right >= right) return query(r->ch[0], left, right);
    else if(r->ch[1]->left <= left) return query(r->ch[1], left, right);
    else
        return query(r->ch[0], left, r->ch[0]->right) + 
               query(r->ch[1], r->ch[1]->left, right);
}
int main()
{
    scanf("%d", &n);
    root = &pool[0];
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    scanf("%d", &m);
    Build_Tree(root, 1, n);
    for(int i = 1; i <= m; i++)
    {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        if(l > r) swap(l, r);
        if(opt) printf("%lld
", query(root, l, r));
        else change(root, l, r);
    }
    return 0;
}