kb-07线段树-08--区间开根

  1 /*
  2    hdu-4027
  3    题目：区间开根求和查询；
  4    因为是开根，所以要更新的话就要更新到叶子节点。如果区间里全是1或是0的话就步用继续更新了，查询的时候正常查询；
  5  */
  6 #include<iostream>
  7 #include<cstring>
  8 #include<cstdio>
  9 #include<cmath>
 10 #define ll long long
 11 using namespace std;
 12 struct Node
 13 {
 14     int l,r;
 15     ll value;
 16     int add;
 17 }tr[400008]={0};
 18 ll n,m,a[100005]={0};
 19 ll ans=0;
 20 void Pushup(int rt)
 21 {
 22     int lson=rt<<1;
 23     int rson=rt<<1|1;
 24     tr[rt].value=tr[lson].value+tr[rson].value;
 25     if(tr[lson].add==1||tr[rson].add==1)
 26         tr[rt].add=1;
 27     else
 28         tr[rt].add=0;
 29 }
 30 void build(int rt,int l,int r)
 31 {
 32     tr[rt].l=l;
 33     tr[rt].r=r;
 34     tr[rt].add=1;
 35     if(l==r)
 36     {
 37         tr[rt].value=a[l];
 38         return ;
 39     }
 40     int mid=(l+r)/2;
 41     build(rt<<1,l,mid);
 42     build(rt<<1|1,mid+1,r);
 43     Pushup(rt);
 44 }
 45 void Update(int rt,int l,int r)
 46 {
 47     if(tr[rt].add==0)//如果区间全是1或0就不更新；
 48         return;
 49     if(tr[rt].l==tr[rt].r&&l==r)//深入到叶子节点开根号；
 50     {
 51         tr[rt].value=(int)sqrt((double)tr[rt].value);
 52         if(tr[rt].value==1||tr[rt].value==0)
 53             tr[rt].add=0;
 54         return ;
 55     }//没有要pusdown的所以没有pushdown
 56     if(l<=tr[rt<<1].r)
 57     {
 58         if(r<=tr[rt<<1].r)
 59             Update(rt<<1,l,r);
 60         else
 61             Update(rt<<1,l,tr[rt<<1].r);
 62     }
 63     if(r>=tr[rt<<1|1].l)
 64     {
 65         if(l>=tr[rt<<1|1].l)
 66             Update(rt<<1|1,l,r);
 67         else 
 68             Update(rt<<1|1,tr[rt<<1|1].l,r);
 69     }
 70     Pushup(rt);
 71 }
 72 void Query(int rt,int l,int r)
 73 {
 74     if(tr[rt].l==l&&tr[rt].r==r)
 75     {
 76         ans+=tr[rt].value;
 77         return ;
 78     }
 79     if(l<=tr[rt<<1].r)
 80     {
 81         if(r<=tr[rt<<1].r)
 82             Query(rt<<1,l,r);
 83         else
 84             Query(rt<<1,l,tr[rt<<1].r);
 85     }
 86     if(r>=tr[rt<<1|1].l)
 87     {
 88         if(l>=tr[rt<<1|1].l)
 89             Query(rt<<1|1,l,r);
 90         else
 91             Query(rt<<1|1,tr[rt<<1|1].l,r);
 92     }
 93 }
 94 int main()
 95 {
 96     int k=1;
 97     while(scanf("%lld",&n)!=EOF)
 98     {
 99         printf("Case #%d:
",k++);
100         memset(a,0,sizeof(a));
101         memset(tr,0,sizeof(tr));
102         for(int i=1;i<=n;i++)
103         {
104             scanf("%lld",&a[i]);
105         }
106         build(1,1,n);
107         scanf("%lld",&m);
108         for(int i=0;i<m;i++)
109         {
110             int x,l,r;
111             scanf("%d%d%d",&x,&l,&r);
112             if(l>r)//输入有坑；
113                 swap(l,r);
114             if(x==0)
115             {
116                 Update(1,l,r);
117             }
118             else
119             {
120                 ans=0;
121                 Query(1,l,r);
122                 printf("%lld
",ans);
123             }
124         }
125         printf("
");
126     }
127     return 0;
128 }