rt,从P4145复制后改的，样例过，RE

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
typedef long long ll;
#define int long long
int lf[N], rt[N], cnt, n, m, CNT;
ll t[N], mx[N], c[N];
void build(int x, int l, int r){
	if(l == r){
		t[x] = mx[x] = c[l];
		return;
	}
	int mid = (l + r) / 2;
	lf[x] = ++cnt, build(lf[x], l, mid), rt[x] = ++cnt, build(rt[x], mid+1, r);
	mx[x] = max(mx[lf[x]], mx[rt[x]]), t[x] = t[lf[x]] + t[rt[x]];
}
void modify(int x, int l, int r, int a, int b){
	if(mx[x] == 1) return;
	if(l == r){
		mx[x] = sqrt(mx[x]), t[x] = mx[x];
		return;
	}
	int mid = (l + r) / 2;
	if(a <= mid) modify(lf[x], l, mid, a, b);
	if(b > mid) modify(rt[x], mid+1, r, a, b);
	t[x] = t[lf[x]] + t[rt[x]], mx[x] = max(mx[lf[x]], mx[rt[x]]);
}
ll query(int x, int l, int r, int a, int b){
	if(a <= l && r <= b) return t[x];
	int mid = (l + r) / 2;
	ll s = 0;
	if(a <= mid) s += query(lf[x], l, mid, a, b);
	if(b > mid) s += query(rt[x], mid+1, r, a, b);
	return s;
}
signed main(){
	//freopen("1.in", "r", stdin);
	
    while(scanf("%lld", &n)){
    	memset(t, 0, sizeof(t));
    	memset(mx, 0, sizeof(mx));
    	memset(lf, 0, sizeof(lf));
    	memset(rt, 0, sizeof(rt));
    	cnt = 1;
        cout<<"Case #"<<++CNT<<":\n";
    	for(int i = 1; i <= n; i++) scanf("%lld", &c[i]);
    	scanf("%lld", &m);
    	build(1, 1, n);
    	while(m--){
    		int i, j, k;
    		scanf("%lld%lld%lld", &i, &j, &k);
    		if(j > k) swap(j, k);
    		if(i == 1) cout<<query(1, 1, n, j, k)<<"\n";
    		else modify(1, 1, n, j, k);
    	}
    	cout<<"\n";
    }
	return 0;
}