给出n个数m个操作， 每个操作有两种， 1是查询[L, R]的和， 2是将[L, R]之间的数变为他们的平方根， 4变成2， 9变成3， 如果不是整数就向下取整， 数据<2^63。
如果一个数是1， 那么它不会变， 一个数不是1， 即使它非常大， 也可以在很少的操作之中变成1。 所以直接更新到叶子节点， 然后用一个数组记录这一个范围用不用更新， 如果全都是1就可以不更新。
另外这题操作时给的范围x, y， x貌似有可能大于y。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define lson l, m, rt<<1 5 #define mem(a) memset(a, 0, sizeof(a)) 6 #define rson m+1, r, rt<<1|1 7 const int maxn = 1e5+5; 8 ll sum[maxn<<2], cnt[maxn<<2]; //cnt数组记录一个范围是否需要更新 9 void pushUp(int rt) { 10 sum[rt] = sum[rt<<1]+sum[rt<<1|1]; 11 cnt[rt] = cnt[rt<<1]&cnt[rt<<1|1]; 12 } 13 void build(int l, int r, int rt) { 14 if(l == r) { 15 scanf("%I64d", &sum[rt]); 16 if(sum[rt]<=1) 17 cnt[rt] = 1; 18 return ; 19 } 20 int m = l+r>>1; 21 build(lson); 22 build(rson); 23 pushUp(rt); 24 } 25 void update(int L, int R, int l, int r, int rt) { 26 if(l == r) { 27 sum[rt] = int(sqrt(sum[rt]*1.0)); 28 if(sum[rt]<=1) 29 cnt[rt] = 1; 30 return ; 31 } 32 int m = l+r>>1; 33 if(L<=m&&!cnt[rt<<1]) 34 update(L, R, lson); 35 if(R>m&&!cnt[rt<<1|1]) 36 update(L, R, rson); 37 pushUp(rt); 38 } 39 ll query(int L, int R, int l, int r, int rt) { 40 if(L<=l&&R>=r) { 41 return sum[rt]; 42 } 43 int m = l+r>>1; 44 ll ret = 0; 45 if(L<=m) 46 ret += query(L, R, lson); 47 if(R>m) 48 ret += query(L, R, rson); 49 return ret; 50 } 51 int main() 52 { 53 int n, m, num = 1;; 54 while(cin>>n) { 55 mem(cnt); 56 build(1, n, 1); 57 cin>>m; 58 printf("Case #%d: ", num++); 59 while(m--) { 60 int sign, x, y; 61 scanf("%d%d%d", &sign, &x, &y); 62 if(x>y) 63 swap(x, y); 64 if(sign) { 65 printf("%I64d ", query(x, y, 1, n, 1)); 66 } else { 67 update(x, y, 1, n, 1); 68 } 69 } 70 cout<<endl; 71 } 72 }