題意：給一個(gè)序列，要求維護(hù)兩個(gè)操作
1：將區(qū)間[L,R]里面的數(shù)開(kāi)方下取整
2：求區(qū)間[L,R]里面元素的和
第一反應(yīng)是線段樹，但是這里面有個(gè)矛盾：開(kāi)方不好處理，如果將序列表示成對(duì)數(shù)，求和又不好處理……
幸運(yùn)的是，開(kāi)方操作收斂的很快，從long long 到 1，只要8次，于是每次對(duì)區(qū)間操作，我們?cè)诰€段樹基礎(chǔ)上進(jìn)行改動(dòng)：線段樹最后將待查詢區(qū)間會(huì)分成Log（N）個(gè)區(qū)間，絕對(duì)不能將操作區(qū)間分成小段……但是現(xiàn)在要這么做，因?yàn)槊總€(gè)點(diǎn)最多被覆蓋8次之后就是1了……于是對(duì)每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)isone標(biāo)記，標(biāo)記這一段是不是1，每次修改都遞歸下去直接修改非1的點(diǎn)，并且維護(hù)isone標(biāo)記……這樣均攤下來(lái)，每個(gè)點(diǎn)最多被改8次……
1 #include <cstdio>
2 #include <cmath>
3 #include <cassert>
4
5 typedef long long Long;
6 Long sum[410000];
7 Long data[110000];
8 bool isone[410000];
9 int n;
10 const int root = 1;
11
12 void build(int now,int left,int right) {
13 if (left == right) {
14 sum[now] = data[left];
15 isone[now] = sum[now] == right - left + 1;
16 } else {
17 int mid = (left + right) >> 1;
18 build(now + now,left,mid);
19 build(now + now + 1,mid + 1,right);
20 sum[now] = sum[now + now] + sum[now + now + 1];
21 isone[now] = sum[now] == right - left + 1;
22 }
23 }
24
25 Long mySqrt(Long x) {
26 double tmp = x;
27 x = Long(sqrt(tmp) + 1e-8);
28 return x;
29 }
30
31 Long getSum(int now,int left,int right,int l,int r) {
32 if (left > r || right < l) return 0;
33 if (l <= left && right <= r) return sum[now];
34 int mid = (left + right) >> 1;
35 return getSum(now + now,left,mid,l,r)
36 + getSum(now + now + 1,mid + 1, right, l, r);
37 }
38
39 void change(int now,int left,int right,int l,int r) {
40 if (left > r || right < l) return;
41 if (isone[now]) return;
42 if (left == right) {
43 sum[now] = mySqrt(sum[now]);
44 isone[now] = sum[now] == right - left + 1;
45 } else {
46 int mid = (left + right) >> 1;
47 change(now + now,left,mid,l,r);
48 change(now + now + 1,mid + 1,right,l,r);
49 sum[now] = sum[now + now] + sum[now + now + 1];
50 isone[now] = sum[now] == right - left + 1;
51 }
52 }
53
54 int main() {
55 int nn = 0;
56 while (scanf("%d",&n) == 1) {
57 for (int i = 0; i < n; i++) {
58 scanf("%lld",data + i);
59 assert(data[i] > 0);
60 }
61 build(root,0,n-1);
62 int m;
63 scanf("%d",&m);
64 printf("Case #%d:\n", ++ nn);
65 while (m--) {
66 int ctrl,l,r;
67 scanf("%d%d%d",&ctrl,&l,&r);
68 l --; r --;
69 if (l > r) {int tmp = l; l = r; r = tmp;}
70 if (ctrl == 1) {
71 printf("%lld\n",getSum(root,0,n-1,l,r));
72 } else {
73 change(root,0,n-1,l,r);
74 }
75 }
76 printf("\n");
77 }
78 return 0;
79 }