[BZOJ3211] 花神游历各国小清新线段树

谁践踏了优雅 2021-11-16 10:14 230阅读 0赞

https://www.lydsy.com/JudgeOnline/problem.php?id=3211

小清新线段树，难在复杂度分析额。

要支持区间开方，区间求和，不带修。 区间开方只能暴力单点修改，看似复杂度不可接受，but....

x开方x1/2相当于对指数进行log级操作，操作次数 log（logx），最坏5次左右到1（初始0除外）。

那么线段树维护一个值用来记录该区间是否有需要更改的点（优化暴力），然后函数暴力递归需要更改的区间到单点修改即可。

修改我开始写了俩函数，一个函数找需要更改的区间（max值），然后更一个更改sum，相当于多了个logn，结果居然还900多ms，改完500多ms呃呃呃。

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define ll long long
    #define reg register
    #define F(i,a,b) for(i=a;i<=b;++i)
    using namespace std;
    ll w1[400005];
    int w2[400005],n;            //1维护和    2维护是否不变 (2为不全为)
    int read()
    {
        reg char c; reg int x=0;
        c=getchar();
        while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
        return x;
    }
    void build1(int k,int l,int r)
    {
        if(l==r)
        {
            w1[k]=read();
            return;
        }
        int mid=(l+r)>>1;
        build1(k<<1,l,mid);
        build1(k<<1|1,mid+1,r);
        w1[k]=w1[k<<1]+w1[k<<1|1];
    }
    void build2(int k,int l,int r)
    {
        if(l==r){
            if(w1[k]<=1) w2[k]=1;
            else w2[k]=2;
            return;
        }
        int mid=(l+r)>>1;
        build2(k<<1,l,mid);
        build2(k<<1|1,mid+1,r);
        w2[k]=max(w2[k<<1],w2[k<<1|1]);
    }
    ll ask(int k,int l,int r,int L,int R)
    {
        ll ans=0;
        if(L<=l&&r<=R) return w1[k];
        int mid=(l+r)>>1;
        if(L<=mid) ans+=ask(k<<1,l,mid,L,R);
        if(R>mid) ans+=ask(k<<1|1,mid+1,r,L,R);
        return ans;
    }
    void ch(int k,int l,int r,int L,int R)
    {
        if(l==r)
        {
            w1[k]=sqrt(w1[k]);
            if(w1[k]<=1) w2[k]=1;
            else w2[k]=2;
            return;
        }
        int mid=(l+r)>>1;
        if(L<=mid&&w2[k<<1]==2) ch(k<<1,l,mid,L,R);
        if(R>mid&&w2[k<<1|1]==2) ch(k<<1|1,mid+1,r,L,R);
        w1[k]=1ll*w1[k<<1]+w1[k<<1|1];
        w2[k]=max(w2[k<<1],w2[k<<1|1]);
    }
    int main()
    {
        int m;
        n=read();
        reg int i,x,l,r;
        build1(1,1,n);
        build2(1,1,n);
        m=read();
        while(m--)
        {
            x=read(); l=read(); r=read();
            if(x==1) printf("%lld\n",ask(1,1,n,l,r));
            else ch(1,1,n,l,r);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hzoi-yzh/p/11008347.html