HDU - 5306 剪枝的线段树

题意：给定\(a[1...n]\)，\(m\)次操作，0表示使\([L,R]\)中的值\(a[i]=min(a[i],x)\),其余的1是查最值2是查区间和

本题是jls的2016论文题，1 2套路不说

对于操作0，维护当前最值和严格次大最值，更新过程分三种情况

1.当前的最大值本来就比\(x\)小或相等，直接剪枝（全局剪枝更优，道理不必多说）

2.当前最大值大于\(x\),次大值小于等于\(x\)，那么影响到的值只有最大值，打个tag维护

3.其它情况，暴力dfs

具体地，\(max\)值的改变影响了\(sum\)值，那我们需要维护的tag需要值为\(max\)的个数，此时\(sum\)只需做差相减

论文证明这种操作下依然是\(O(logn)\)的

代码改得比较多，略丑

细节要注意的地方也挺多的

#include<bits/stdc++.h>

#define rep(i,j,k) for(register int i=j;i<=k;i++)

#define rrep(i,j,k) for(register int i=j;i>=k;i--)

#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])

#define print(a) printf("%lld",(ll)a)

#define println(a) printf("%lld\n",(ll)(a))

using namespace std;

const int MAXN = 1e6+11;

const int NN = 1e5+11;

const int INF = 0x3f3f3f3f;

const double EPS = 1e-7;

typedef long long ll;

const ll MOD = 1e9+7;

ll read() {

    ll x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int a[MAXN];

struct ST{

    #define lc o<<1

    #define rc o<<1|1

    int mx[MAXN<<2],smx[MAXN<<2],mxcnt[MAXN<<2];

    ll sum[MAXN<<2];

    bool lazy[MAXN<<2];

    void pu(int o){

        mx[o]=max(mx[lc],mx[rc]);

        sum[o]=sum[lc]+sum[rc];

        smx[o]=max(smx[lc],smx[rc]);

        mxcnt[o]=0;

        if(mx[lc]!=mx[rc]) smx[o]=max(smx[o],min(mx[lc],mx[rc]));//

        if(mx[lc]==mx[o]) mxcnt[o]+=mxcnt[lc];

        if(mx[rc]==mx[o]) mxcnt[o]+=mxcnt[rc];

    }

    void pd(int o){

        if(lazy[o]){

            if(mx[lc]>mx[o]){

                lazy[lc]=1;

                sum[lc]-=1ll*(mx[lc]-mx[o])*mxcnt[lc];

                mx[lc]=mx[o];

            }

            if(mx[rc]>mx[o]){

                lazy[rc]=1;

                sum[rc]-=1ll*(mx[rc]-mx[o])*mxcnt[rc];

                mx[rc]=mx[o];

            }

            lazy[o]=0;

            // lazy[lc]=lazy[rc]=1;

        }

    }

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

        mx[o]=smx[o]=-INF;mxcnt[o]=lazy[o]=sum[o]=0;

        if(l==r){

            sum[o]=mx[o]=a[l];

            // smx[o]=-INF;

            mxcnt[o]=1;

            return;

        }

        int mid=l+r>>1;

        build(lc,l,mid);

        build(rc,mid+1,r);

        pu(o);

    }

    void update(int o,int l,int r,int L,int R,int v){

        if(mx[o]<=v) return; // 全局剪枝

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

            // if(mx[o]<=v)return;

            if(smx[o]<=v){//只改变最大值

                // pd(o);

                lazy[o]=1;

                sum[o]-=1ll*(mx[o]-v)*mxcnt[o];

                mx[o]=v;//mxcnt bu bian

                return;

            }

        }

        pd(o);

        int mid=l+r>>1;

        if(L<=mid) update(lc,l,mid,L,R,v);

        if(R>mid) update(rc,mid+1,r,L,R,v);

        pu(o);

    }

    ll queryMax(int o,int l,int r,int L,int R){

        if(L<=l&&r<=R) return mx[o];

        pd(o);

        int mid=l+r>>1;

        ll res=-INF;

        if(L<=mid) res=max(res,queryMax(lc,l,mid,L,R));

        if(R>mid) res=max(res,queryMax(rc,mid+1,r,L,R));

        return res;

    }

    ll querySum(int o,int l,int r,int L,int R){

        if(L<=l&&r<=R) return sum[o];

        pd(o);

        int mid=l+r>>1;

        ll res=0;

        if(L<=mid) res+=querySum(lc,l,mid,L,R);

        if(R>mid) res+=querySum(rc,mid+1,r,L,R);

        return res;

    }

}st;

int main(){

    int T=read();

    while(T--){

        int n=read();

        int m=read();

        rep(i,1,n) a[i]=read();

        st.build(1,1,n);

        rep(i,1,m){

            int op=read();

            int x=read();

            int y=read();

            if(op==0){

                int t=read();

                st.update(1,1,n,x,y,t);

            }else if(op==1){

                println(st.queryMax(1,1,n,x,y));

            }else{

                println(st.querySum(1,1,n,x,y));

            }

        }

    }

    return 0;

}

巴特西

HDU - 5306 剪枝的线段树

最新文章

热门文章