hdu 4027 2011上海赛区网络赛G 线段树 成段平方根 ***

不能直接使用成段增减的那种，因为一段和的平方根不等于平方根的和，直接记录是否为1，是1就不需要更新了

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define root 1,n,1

 #define mid ((l+r)>>1)

 const int MAXN=;

 int n,m,t,Min;

 ll sum[MAXN<<];

 int col[MAXN<<];

 void pushup(int rt)

 {

     sum[rt]=sum[rt<<]+sum[rt<<|];

     col[rt]=col[rt<<]&&col[rt<<|];

 }

 void build(int l,int r,int rt){

     col[rt]=;

     if(l==r)

     {

         scanf("%I64d",&sum[rt]);

         return;

     }

     build(lson);

     build(rson);

     pushup(rt);

 }

 void update(int L,int R,int l,int r,int rt)

 {

     if(l==r)

     {

         sum[rt]=sqrt(sum[rt]);

         if(sum[rt]==)  col[rt]=;

         return;

     }

     if(L<=mid&&!col[rt<<])  update(L,R,lson);

     if(R>mid&&!col[rt<<|]) update(L,R,rson);

     pushup(rt);

 }

 ll query(int L,int R,int l,int r,int rt)

 {

     if(l>=L&&r<=R)

     {

         return sum[rt];

     }

     ll ans=;

     if(L<=mid)  ans+=query(L,R,lson);

     if(R>mid) ans+=query(L,R,rson);

     return ans;

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     int ca=;

     while(scanf("%d",&n)!=EOF)

     {

         build(root);

         int q;

         scanf("%d",&q);

         printf("Case #%d:\n",ca++);

         int s,L,R;

         while(q--)

         {

             scanf("%d%d%d",&s,&L,&R);

             if(L>R) swap(L,R);

             if(s==)

             {

                 update(L,R,root);

             }

             else

             {

                 ll w=query(L,R,root);

                 printf("%I64d\n",w);

             }

         }

         printf("\n");

     }

 }