题意：给一个序列，要求维护两个操作
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 }