【SPOJ】2713 Can you answer these queries IV

操作：

1，把[x,y]每个数k变成sqrt(k)，向下取整。

2，查询区间的和。

就算10^18，sqrt后减少的很快。

当一个数为0或1时，它不会再变化了，把不会变化的区间标记，不再访问。

所以暴力更新总的可以视为O(nlogn)的。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #define EPS 1e-8
 5 #define MAXN 100010
 6 typedef long long LL;
 7 using namespace std;
 8 struct node {
 9     LL sum;
10     bool flag;
11 };
12 node tree[MAXN << 2];
13 inline void PushUp(int rt) {
14     tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
15     tree[rt].flag = tree[rt << 1].flag & tree[rt << 1 | 1].flag;
16 }
17 void Build(int L, int R, int rt) {
18     if (L == R) {
19         scanf("%lld", &tree[rt].sum);
20         if (tree[rt].sum == 1 || tree[rt].sum == 0)
21             tree[rt].flag = true;
22         else
23             tree[rt].flag = false;
24     } else {
25         int mid = (L + R) >> 1;
26         Build(L, mid, rt << 1);
27         Build(mid + 1, R, rt << 1 | 1);
28         PushUp(rt);
29     }
30 }
31 LL Query(int x, int y, int L, int R, int rt) {
32     if (x <= L && R <= y)
33         return tree[rt].sum;
34     int mid = (L + R) >> 1;
35     LL ans = 0;
36     if (x <= mid)
37         ans += Query(x, y, L, mid, rt << 1);
38     if (y > mid)
39         ans += Query(x, y, mid + 1, R, rt << 1 | 1);
40     return ans;
41 }
42 void Update(int x, int y, int L, int R, int rt) {
43     if (tree[rt].flag)
44         return;
45     if (L == R) {
46         tree[rt].sum = (LL) (sqrt((double) tree[rt].sum) + EPS);
47         if (tree[rt].sum == 1)
48             tree[rt].flag = true;
49     } else {
50         int mid = (L + R) >> 1;
51         if (x <= mid)
52             Update(x, y, L, mid, rt << 1);
53         if (y > mid)
54             Update(x, y, mid + 1, R, rt << 1 | 1);
55         PushUp(rt);
56     }
57 }
58 int main() {
59     int ca = 1;
60     int n, q, cmd, x, y;
61     while (~scanf("%d", &n)) {
62         printf("Case #%d:\n", ca++);
63         Build(1, n, 1);
64         scanf("%d", &q);
65         while (q--) {
66             scanf("%d%d%d", &cmd, &x, &y);
67             if (x > y)
68                 swap(x, y);
69             if (cmd)
70                 printf("%lld\n", Query(x, y, 1, n, 1));
71             else
72                 Update(x, y, 1, n, 1);
73         }
74         putchar('\n');
75     }
76     return 0;
77 }