Can you answer these queries?（HDU4027+势能线段树）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027

题目：

题意：n个数，每次区间更新将其数值变成它的根号倍（向下取整），区间查询数值和。

思路：易知这题的lazy标记是不好打的，但是我们发现当这个数取根号直到变成1时就不需要更新了，像这种无法打标记并且经过多次操作后就不需要操作的线段树叫做势能线段树。在需要更新时我们一直暴力到它的叶子节点，当某个区间无法更新时我们将其的flag设为0，对于某个节点的flag就等于它的左右子节点的flag取或。

代码实现如下：

  1 #include <set>
  2 #include <map>
  3 #include <queue>
  4 #include <stack>
  5 #include <cmath>
  6 #include <bitset>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <iostream>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 typedef long long ll;
 17 typedef unsigned long long ull;
 18 
 19 #define lson i<<1,l,mid
 20 #define rson i<<1|1,mid+1,r
 21 #define bug printf("*********
");
 22 #define FIN freopen("D://code//in.txt", "r", stdin);
 23 #define debug(x) cout<<"["<<x<<"]" <<endl;
 24 #define IO ios::sync_with_stdio(false),cin.tie(0);
 25 
 26 const double eps = 1e-8;
 27 const int mod = 1e8;
 28 const int maxn = 1e5 + 7;
 29 const double pi = acos(-1);
 30 const int inf = 0x3f3f3f3f;
 31 const ll INF = 0x3f3f3f3f3f3f3f3f;
 32 
 33 inline int read() {//读入挂
 34     int ret = 0, c, f = 1;
 35     for(c = getchar(); !(isdigit(c) || c == '-'); c = getchar());
 36     if(c == '-') f = -1, c = getchar();
 37     for(; isdigit(c); c = getchar()) ret = ret * 10 + c - '0';
 38     if(f < 0) ret = -ret;
 39     return ret;
 40 }
 41 
 42 int n, q, op, x, y;
 43 
 44 struct node {
 45     int l, r, flag;
 46     ll sum;
 47 }segtree[maxn*4];
 48 
 49 void push_up(int i) {
 50     segtree[i].sum = segtree[i*2].sum + segtree[i*2+1].sum;
 51     segtree[i].flag = segtree[i*2].flag | segtree[i*2+1].flag;
 52 }
 53 
 54 void build(int i, int l, int r) {
 55     segtree[i].l = l, segtree[i].r = r, segtree[i].flag = 1;
 56     if(l == r) {
 57         scanf("%lld", &segtree[i].sum);
 58         if(segtree[i].sum <= 1) segtree[i].flag = 0;
 59         return;
 60     }
 61     int mid = (l + r) >> 1;
 62     build(lson);
 63     build(rson);
 64     push_up(i);
 65 }
 66 
 67 void update(int i, int l, int r) {
 68     if(!segtree[i].flag) return;
 69     if(segtree[i].l == segtree[i].r) {
 70         if(segtree[i].flag) {
 71             segtree[i].sum = sqrt(segtree[i].sum);
 72             if(segtree[i].sum <= 1) segtree[i].flag = 0;
 73         }
 74         return;
 75     }
 76     int mid = (segtree[i].l + segtree[i].r) >> 1;
 77     if(r <= mid) {
 78         if(segtree[i*2].flag)
 79             update(i*2, l, r);
 80     }
 81     else if(l > mid) {
 82         if(segtree[i*2+1].flag)
 83             update(i*2+1, l, r);
 84     }
 85     else {
 86         if(segtree[i*2].flag) update(lson);
 87         if(segtree[i*2+1].flag) update(rson);
 88     }
 89     push_up(i);
 90 }
 91 
 92 ll query(int i, int l, int r) {
 93     if(segtree[i].l == l && segtree[i].r == r) {
 94         return segtree[i].sum;
 95     }
 96     int mid = (segtree[i].l + segtree[i].r) >> 1;
 97     if(l > mid) return query(i * 2 + 1, l, r);
 98     else if(r <= mid) return query(i * 2, l, r);
 99     else return query(lson) + query(rson);
100 }
101 
102 int main() {
103     //FIN;
104     int icase = 0;
105     while(~scanf("%d", &n)) {
106         build(1, 1, n);
107         printf("Case #%d:
", ++icase);
108         scanf("%d", &q);
109         while(q--) {
110             scanf("%d%d%d", &op, &x, &y);
111             int a = max(x, y), b = min(x, y);
112             if(op == 0) {
113                 update(1, b, a);
114             } else {
115                 printf("%lld
", query(1, b, a));
116             }
117         }
118         printf("
");
119     }
120     return 0;
121 }