HDU 4027 Can you answer these queries

题目链接

题意：给定一个数列，两种操作

0 a b 把[a,b]区间内的数字都开根
1 a b 询问区间[a,b]和

思路：注意开根最多开到1或0就不在变化，那么一个数字最多开63次，然后题目保证数列和小于2^63，所以实际上对于每个数字的修改总次数并不多，因此修改操作每次就单点修改，线段树多开一个标记，表示这个区间是否全部都已经不变了

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; const int N = 100005; #define lson(x) ((x<<1)+1) #define rson(x) ((x<<1)+2) struct Node { int l, r; ll sum; bool cover; } node[4 * N]; int n; void pushup(int x) { node[x].cover = (node[lson(x)].cover && node[rson(x)].cover); node[x].sum = node[lson(x)].sum + node[rson(x)].sum; } void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; node[x].cover = false; if (l == r) { scanf("%I64d", &node[x].sum); if (node[x].sum == 0 || node[x].sum == 1) node[x].cover = true; return; } int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); pushup(x); } void add(int l, int r, int x = 0) { if (node[x].cover) return; if (node[x].l == node[x].r) { node[x].sum = (ll)sqrt(node[x].sum * 1.0); if (node[x].sum == 1) node[x].cover = true; return; } int mid = (node[x].l + node[x].r) / 2; if (l <= mid) add(l, r, lson(x)); if (r > mid) add(l, r, rson(x)); pushup(x); } ll query(int l, int r, int x = 0) { if (node[x].l >= l && node[x].r <= r) return node[x].sum; int mid = (node[x].l + node[x].r) / 2; ll ans = 0; if (l <= mid) ans += query(l, r, lson(x)); if (r > mid) ans += query(l, r, rson(x)); return ans; } int main() { int cas = 0; while (~scanf("%d", &n)) { build(1, n); scanf("%d", &n); int op, a, b; printf("Case #%d:\n", ++cas); while (n--) { scanf("%d%d%d", &op, &a, &b); if (a > b) swap(a, b); if (op == 0) add(a, b); else printf("%I64d\n", query(a, b)); } printf("\n"); } return 0; }