hdu 4027（线段树开根号）

旧城等待， 2023-06-03 13:00 34阅读 0赞

线段树开根号，更新的时候加一个剪枝就行了（本来用lazy标记区间开更好的次数，wa了好几发）。。。如果下面的和等于区间的长度就不用再往下开根号了，因为这时的区间全为1；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <string>
    using namespace std;
    const int maxn=1e5+10;
    const int inf=0x3f3f3f3f;
    typedef long long ll;
    ll a[maxn],tree[maxn*4];
    void build(int l,int r,int now){
        if(l==r){
            tree[now]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,now<<1);
        build(mid+1,r,now<<1|1);
        tree[now]=tree[now<<1]+tree[now<<1|1];
    }
    void o2(int l,int r,int now,int L,int R){
        if(l==r){
            tree[now]=sqrt(tree[now]);
            //lazy[now]++;
            return;
        }
        if(l>=L&&r<=R&&(tree[now]==(r-l+1)))return;
        int mid=(l+r)>>1;
        if(mid>=L)o2(l,mid,now<<1,L,R);
        if(mid<R)o2(mid+1,r,now<<1|1,L,R);
        tree[now]=tree[now<<1]+tree[now<<1|1];
    }
    ll o1(int l,int r,int now,int L,int R){
        if(l>=L&&r<=R){
            return tree[now];
        }
        int mid=(l+r)>>1;
        ll sum=0;
        if(L<=mid)sum+=o1(l,mid,now<<1,L,R);
        if(R>mid)sum+=o1(mid+1,r,now<<1|1,L,R);
        return sum;
    }
    int main(){
        //ios::sync_with_stdio(false);
        int flag=0;
        int n;
        while(~scanf("%d",&n)){
            //memset(lazy,0,sizeof(lazy));
            printf("Case #%d:\n",++flag);
            for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
            build(1,n,1);
            int m;
            scanf("%d",&m);
            while(m--){
                int op,x,y;
                scanf("%d%d%d",&op,&x,&y);
                if(op==0){
                    o2(1,n,1,min(x,y),max(x,y));
                }
                else if(op==1){
                    printf("%lld\n",o1(1,n,1,min(x,y),max(x,y)));
                }
            }
            printf("\n");
        }
    
    
    
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11287104.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/7caefd7d773c429fbcd2e380cec87b6e.png