前50ptsAC 后50ptsRE

#include <bits/stdc++.h>

#define MAXN 1048577
#define int long long

using namespace std;

struct node {
	int l, r, s, m;
	node * ch[2];
};

int n, m, arr[MAXN << 4], cnt;
node tree[MAXN << 4];
node * root;

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

void build(node * rot, int l, int r) {
	rot->l = l;
	rot->r = r;
	if (l == r) {
		rot->s = arr[l];
		rot->m = arr[r];
		return;
	}
	int mid = (l + r) >> 1;
	node * ls = &tree[++cnt];
	node * rs = &tree[++cnt];
	rot->ch[0] = ls;
	rot->ch[1] = rs;
	build(rot->ch[0], l, mid);
	build(rot->ch[1], mid + 1, r);
	pushup(rot);
}

void sqr(node * rot, int l, int r) {
	if (rot->l == rot->r) {
		rot->s = (int) sqrt(rot->s);
		rot->m = (int) sqrt(rot->m);
		return;
	}
	int mid = (rot->l + rot->r) >> 1;
	if (l <= mid && rot->ch[0]->m > 1) {
		sqr(rot->ch[0], l, r);
	} 
	if (mid < r && rot->ch[1]->m > 1) {
		sqr(rot->ch[1], l, r);
	}
	pushup(rot);
}

int get(node * rot, int l, int r) {
	if (rot->l == l && rot->r == r) return rot->s;
	if (rot->ch[0]->r >= r) return get(rot->ch[0], l, r);
	else if (rot->ch[1]->l <= l) return get(rot->ch[1], l, r);
	else return get(rot->ch[0], l, rot->ch[0]->r) + get(rot->ch[1], rot->ch[1]->l, r);
}

signed main()
{
    int op, x, y;
    root = &tree[0];
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

    build(root, 1, n);
	
	cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> op >> x >> y;
        if (op == 0)
        {
            sqr(root, x, y);
        }
        else
        {
			cout << get(root, x, y) << endl;            
        }
    }
    return 0;
}

求调。