HDU-4027-Can you answer these qu

思路：

• 题目中的每次改值都是变成原来的平方根，然而平方根好像没有求和公式啥的，，找不出来。而且发现很大的数经过几次操作后会变成，之后它再被操作它还是。于是有这个那只有单点改值了，就是将区间的每一个数不为的数都操作一次。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=100010;
struct node
{
    int l,r;
    int op;
    ll sum;
}tree[M<<2];
void pushup(int root)
{
    tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
    tree[root].op=(tree[root<<1].op&&(tree[root<<1|1].op));//区间的左子树和右子树都为1，这个区间才为1
}
void build(int l,int r,int root)
{
    tree[root].op=0;
    tree[root].sum=0;
    tree[root].l=l;
    tree[root].r=r;
    if(l==r)
    {
        scanf("%lld",&tree[root].sum);
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    pushup(root);
}
void update(int l,int r,int root,int x,int y)
{
    if(tree[root].op==1)
    {
        return;
    }
    if(l==r)//找到区间x~y的每个叶节点
    {
        tree[root].sum=sqrt(tree[root].sum);
        if(tree[root].sum==1)
        {
            tree[root].op=1;
        }
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid)
    {
        update(l,mid,root<<1,x,y);
    }
    if(y>mid)
    {
        update(mid+1,r,root<<1|1,x,y);
    }
    pushup(root);
}
ll query(int l,int r,int root,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return tree[root].sum;
    }
    ll ans=0;
    int mid=l+r>>1;
    if(x<=mid)
    {
        ans+=query(l,mid,root<<1,x,y);
    }
    if(y>mid)
    {
        ans+=query(mid+1,r,root<<1|1,x,y);
    }
    return ans;
}
int main( )
{
    int n,m,t,x,y;
    int k=0;
    while(scanf("%d",&n)!=EOF)
    {
        k++;
        build(1,n,1);
        cout<<"Case #"<<k<<":"<<endl;
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>t>>x>>y;
            if(x>y)
            {
                swap(x,y);
            }
            if(t==0)
            {
                update(1,n,1,x,y);
            }
            else
            {
                cout<<query(1,n,1,x,y)<<endl;
            }   
        }
        cout<<endl;
    }
    return 0;
}