題意：給一個序列，要求維護兩個操作
1：將區間[L,R]里面的數開方下取整
2：求區間[L,R]里面元素的和
第一反應是線段樹，但是這里面有個矛盾：開方不好處理，如果將序列表示成對數，求和又不好處理……
幸運的是，開方操作收斂的很快，從long long 到 1，只要8次，于是每次對區間操作，我們在線段樹基礎上進行改動：線段樹最后將待查詢區間會分成Log（N）個區間，絕對不能將操作區間分成小段……但是現在要這么做，因為每個點最多被覆蓋8次之后就是1了……于是對每個節點維護一個isone標記，標記這一段是不是1，每次修改都遞歸下去直接修改非1的點，并且維護isone標記……這樣均攤下來，每個點最多被改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 }