cf102012E. Rikka with Data Structures

题目描述

题解

楼房重建的提高版。

用线段树维护每个区间的单调不下降的元素个数。

我们可以考虑假设左区间和右区间的个数已经知道了，现在要合并。

所以要用左区间的最大值 $v$ 来计算右区间能加进来的个数。

于是递归右区间，如果其左区间的最大值小于 $v$ ，那就递归右区间，否则递归左区间再加上右区间的个数即可。

右区间的个数就是区间个数-左区间个数。

效率： $O(nlog^2n)$ 。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
int T,n,m;
LL A[N];
struct O{int k,l,r;};
struct Tree{
    LL a[N],t[N<<2],ad[N<<2],tg[N<<2];
    int p[N<<2],c;
    O g[30];
#define Ls k<<1
#define Rs k<<1|1
#define mid ((l+r)>>1)
    void pushtg(int k,LL v,int l,int r){
        t[k]=v;tg[k]=v;ad[k]=0;p[k]=r-l+1;
    }
    void pushad(int k,LL v){
        t[k]+=v;ad[k]+=v;
    }
    void down(int k,int l,int r){
        if (tg[k])
            pushtg(Ls,tg[k],l,mid),
            pushtg(Rs,tg[k],mid+1,r),tg[k]=0;
        if (ad[k])
            pushad(Ls,ad[k]),
            pushad(Rs,ad[k]),ad[k]=0;
    }
    int qry(int k,int l,int r,LL v){
        if (l==r) return t[k]>=v;
        down(k,l,r);
        if (v>t[Ls]) return qry(Rs,mid+1,r,v);
        return qry(Ls,l,mid,v)+p[k]-p[Ls];
    }
    void up(int k,int l,int r){
        t[k]=max(t[Ls],t[Rs]);
        p[k]=p[Ls]+qry(Rs,mid+1,r,t[Ls]);
    }
    void build(int k,int l,int r){
        ad[k]=tg[k]=0;
        if (l==r){t[k]=a[l];p[k]=1;return;}
        build(Ls,l,mid);build(Rs,mid+1,r);up(k,l,r);
    }
    void updad(int k,int l,int r,int L,int R,int v){
        if (L<=l && r<=R) return pushad(k,v);
        down(k,l,r);
        if (mid>=L) updad(Ls,l,mid,L,R,v);
        if (mid<R) updad(Rs,mid+1,r,L,R,v);
        up(k,l,r);
    }
    void updtg(int k,int l,int r,int L,int R,int v){
        if (L<=l && r<=R) return pushtg(k,v,l,r);
        down(k,l,r);
        if (mid>=L) updtg(Ls,l,mid,L,R,v);
        if (mid<R) updtg(Rs,mid+1,r,L,R,v);
        up(k,l,r);
    }
    void find(int k,int l,int r,int L,int R){
        if (L<=l && r<=R){
            g[++c]=(O){k,l,r};
            return;
        }
        down(k,l,r);
        if (mid>=L) find(Ls,l,mid,L,R);
        if (mid<R) find(Rs,mid+1,r,L,R);
    }
    int get(int l,int r,LL v){
        if (l>r) return 0;
        c=0;find(1,1,n,l,r);
        int u=0;
        for (int i=1;i<=c;i++)
            u+=qry(g[i].k,g[i].l,g[i].r,v),
            v=max(v,t[g[i].k]);
        return u;
    }
    LL qry(int k,int l,int r,int L,int R){
        if (L<=l && r<=R) return t[k];
        down(k,l,r);
        if (mid>=R) return qry(Ls,l,mid,L,R);
        if (mid<L) return qry(Rs,mid+1,r,L,R);
        return max(qry(Ls,l,mid,L,R),qry(Rs,mid+1,r,L,R));
    }
    int ef(int k,int l,int r,int L,int R,LL v){
        if (l==r) return l+(t[k]<=v);
        down(k,l,r);
        if (mid<L) return ef(Rs,mid+1,r,L,R,v);
        if (mid>=R) return ef(Ls,l,mid,L,R,v);
        if (qry(Ls,l,mid,L,mid)<=v)
            return ef(Rs,mid+1,r,L,R,v);
        return ef(Ls,l,mid,L,R,v);
    }
    int Get(int x,int l,int r){
        if (l>r) return 0;
        LL w=qry(1,1,n,x,x);
        int u=get(x,r,w);
        int v=ef(1,1,n,l,r,w);
        int y=get(x,v-1,w);
        return u+v-l-y;
    }
}t1,t2;
void work(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%lld",&A[i]),
        t1.a[i]=A[i],t2.a[n-i+1]=A[i];
    t1.build(1,1,n);t2.build(1,1,n);
    for (int op,l,r,x;m--;){
        scanf("%d%d%d%d",&op,&l,&r,&x);
        if (op==1){
            t1.updad(1,1,n,l,r,x);
            t2.updad(1,1,n,n-r+1,n-l+1,x);
        }
        else if (op==2){
            t1.updtg(1,1,n,l,r,x);
            t2.updtg(1,1,n,n-r+1,n-l+1,x);
        }
        else{
            if (x<l) printf("%d
",t1.Get(x,x+1,r)-t1.Get(x,x+1,l-1));
            else if (x>r) printf("%d
",t2.Get(n-x+1,n-x+2,n-l+1)-t2.Get(n-x+1,n-x+2,n-r));
            else printf("%d
",t1.Get(x,x+1,r)+t2.Get(n-x+1,n-x+2,n-l+1)+1);
        }
    }
}
int main(){
    for (scanf("%d",&T);T--;work());
    return 0;
}