hdu 4027 Can you answer these queries?

http://acm.hdu.edu.cn/showproblem.php?pid=4027

x可能比y大。区间的每一个数在经过几次开方之后会变成1之后，在这个区间全部变成1之后，这个区间不用向下更新。这里可以判断一下。。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <algorithm>
  5 #define maxn 100010
  6 #define ll __int64
  7 using namespace std;
  8 
  9 ll a[maxn];
 10 int n,m;
 11 int op,x,y;
 12 struct node
 13 {
 14     int l,r;
 15     ll sum;
 16 }tree[maxn*4];
 17 
 18 void build(int i,int l,int r)
 19 {
 20     tree[i].l=l;
 21     tree[i].r=r;
 22     if(l==r)
 23     {
 24         tree[i].sum=a[l];
 25         return ;
 26     }
 27     int mid=(l+r)>>1;
 28     build(i<<1,l,mid);
 29     build(i<<1|1,mid+1,r);
 30     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 31 }
 32 
 33 void update(int i,int l,int r)
 34 {
 35     if(tree[i].l==l&&tree[i].r==r&&tree[i].sum==tree[i].r-tree[i].l+1) return;
 36     if(tree[i].l==tree[i].r)
 37     {
 38         tree[i].sum=sqrt(tree[i].sum*1.0);
 39         return ;
 40     }
 41     int mid=(tree[i].l+tree[i].r)>>1;
 42     if(r<=mid)
 43     {
 44         update(i<<1,l,r);
 45     }
 46     else if(l>mid)
 47     {
 48         update(i<<1|1,l,r);
 49     }
 50     else
 51     {
 52         update(i<<1,l,mid);
 53         update(i<<1|1,mid+1,r);
 54     }
 55     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 56 }
 57 
 58 ll search1(int i,int l,int r)
 59 {
 60     if(tree[i].l==l&&tree[i].r==r)
 61     {
 62         return tree[i].sum;
 63     }
 64     int mid=(tree[i].l+tree[i].r)>>1;
 65     if(r<=mid)
 66     {
 67         return search1(i<<1,l,r);
 68     }
 69     else if(l>mid)
 70     {
 71         return search1(i<<1|1,l,r);
 72     }
 73     else
 74     {
 75         return search1(i<<1,l,mid)+search1(i<<1|1,mid+1,r);
 76     }
 77 }
 78 
 79 
 80 int main()
 81 {
 82     int cas=1;
 83     while(scanf("%d",&n)!=EOF)
 84     {
 85         for(int i=1; i<=n; i++)
 86         {
 87             scanf("%I64d",&a[i]);
 88         }
 89         build(1,1,n);
 90         scanf("%d",&m);
 91         printf("Case #%d:
",cas);
 92         cas++;
 93         for(int i=1; i<=m; i++)
 94         {
 95             scanf("%d%d%d",&op,&x,&y);
 96             if(x>y) swap(x,y);
 97             if(op==0)
 98             {
 99                 update(1,x,y);
100             }
101             else if(op==1)
102             {
103                 printf("%I64d
",search1(1,x,y));
104             }
105         }
106         printf("
");
107     }
108     return 0;
109 }

View Code