线段树维护区间最值操作与区间历史最值

luckydrawbox · 2022-05-28 20:01:28 · 个人记录

宏定义

常量与变量

函数

代码

#define pl p<<1
#define pr p<<1|1
struct Segment_Tree{
    long long inf=2e9;
    struct Tree{
        long long mxa,cnt,mxb,se,sum;
        long long mxtag1,setag1,mxtag2,setag2;
    }a[N<<2];
    void pushup(int p){
        a[p].sum=a[pl].sum+a[pr].sum;
        a[p].mxa=max(a[pl].mxa,a[pr].mxa);
        a[p].mxb=max(a[pl].mxb,a[pr].mxb);
        if(a[pl].mxa==a[pr].mxa){
            a[p].se=max(a[pl].se,a[pr].se);
            a[p].cnt=a[pl].cnt+a[pr].cnt;
        }
        else if(a[pl].mxa>a[pr].mxa){
            a[p].se=max(a[pl].se,a[pr].mxa);
            a[p].cnt=a[pl].cnt;
        }
        else{
            a[p].se=max(a[pl].mxa,a[pr].se);
            a[p].cnt=a[pr].cnt;
        }
    }
    void update(int p,int L,int R,long long t1,long long st1,long long t2,long long st2){
        a[p].sum+=t1*a[p].cnt+st1*(R-L+1-a[p].cnt);
        a[p].mxb=max(a[p].mxb,a[p].mxa+t2);
        a[p].mxtag2=max(a[p].mxtag2,a[p].mxtag1+t2);
        a[p].setag2=max(a[p].setag2,a[p].setag1+st2);
        a[p].mxa+=t1;
        a[p].mxtag1+=t1;
        a[p].setag1+=st1;
        if(a[p].se!=-inf)
            a[p].se+=st1;
    }
    void pushdown(int p,int L,int R){
        ll mx=max(a[pl].mxa,a[pr].mxa);
        int mid=(L+R)>>1;
        if(a[pl].mxa==mx)
            update(pl,L,mid,a[p].mxtag1,a[p].setag1,a[p].mxtag2,a[p].setag2);
        else
            update(pl,L,mid,a[p].setag1,a[p].setag1,a[p].setag2,a[p].setag2);
        if(a[pr].mxa==mx)
            update(pr,mid+1,R,a[p].mxtag1,a[p].setag1,a[p].mxtag2,a[p].setag2);
        else
            update(pr,mid+1,R,a[p].setag1,a[p].setag1,a[p].setag2,a[p].setag2);
        a[p].mxtag1=a[p].setag1=a[p].mxtag2=a[p].setag2=0;
    }
    void build(int p,int L,int R){
        if(L==R){
            a[p].sum=a[p].mxa=a[p].mxb=b[L];
            a[p].cnt=1;
            a[p].se=-inf;
            return;
        }
        int mid=(L+R)>>1;
        build(pl,L,mid);
        build(pr,mid+1,R);
        pushup(p);
    }
    void add(int p,int L,int R,int l,int r,long long v){
        if(l<=L&&R<=r){
            update(p,L,R,v,v,v,v);
            return;
        }
        pushdown(p,L,R);
        int mid=(L+R)>>1;
        if(l<=mid)
            add(pl,L,mid,l,r,v);
        if(r>mid)
            add(pr,mid+1,R,l,r,v);
        pushup(p);
    }
    void domin(int p,int L,int R,int l,int r,long long v){
        if(v>=a[p].mxa)
            return;
        if(l<=L&&R<=r&&v>a[p].se){
            update(p,L,R,v-a[p].mxa,0,v-a[p].mxa,0);
            return;
        }
        pushdown(p,L,R);
        int mid=(L+R)>>1;
        if(l<=mid)
            domin(pl,L,mid,l,r,v);
        if(r>mid)
            domin(pr,mid+1,R,l,r,v);
        pushup(p);
    }
    long long asksum(int p,int L,int R,int l,int r){
        if(l<=L&&R<=r)
            return a[p].sum;
        pushdown(p,L,R);
        int mid=(L+R)>>1;
        ll ans=0;
        if(l<=mid)
            ans+=asksum(pl,L,mid,l,r);
        if(r>mid)
            ans+=asksum(pr,mid+1,R,l,r);
        return ans;
    }
    long long askmxa(int p,int L,int R,int l,int r){
        if(l<=L&&R<=r)
            return a[p].mxa;
        pushdown(p,L,R);
        int mid=(L+R)>>1;
        ll ans=-inf;
        if(l<=mid)
            ans=max(ans,askmxa(pl,L,mid,l,r));
        if(r>mid)
            ans=max(ans,askmxa(pr,mid+1,R,l,r));
        return ans;
    }
    long long askmxb(int p,int L,int R,int l,int r){
        if(l<=L&&R<=r)
            return a[p].mxb;
        pushdown(p,L,R);
        int mid=(L+R)>>1;
        ll ans=-inf;
        if(l<=mid)
            ans=max(ans,askmxb(pl,L,mid,l,r));
        if(r>mid)
            ans=max(ans,askmxb(pr,mid+1,R,l,r));
        return ans;
    }
}tree;