树套树(权值线段树套区间线段树)

墨蓝 2023-08-17 17:27 55阅读 0赞

有N个位置，M个操作。操作有两种，每次操作如果是：

*  `1 a b c`：表示在第a个位置到第b个位置，每个位置加上一个数c
 *  `2 a b c`：表示询问从第a个位置到第b个位置，第C大的数是多少。

思路：  
将所有的要加的数字离散化\[1  tot \]，建立一个tot个叶子的权值线段树。

权值线段树中每个点都是一个区间线段树，

在权值线段树中  ，叶子节点的含义是：这个权值对应的位置区间都被修改  
                            非叶子节点的含义是：在当前权值区间中，对应的位置区间被修改

查询的时候，就相当于二分答案：每到一个点，取一个mid，算一下在指定区间内，大于这个mid的数字有多少。

代码模板：

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<iostream>
    #include<ctime>
    #define rint register int
    using namespace std;
    typedef long long ll;
    const int inf = 0x7fffffff;
    const int N=5e4+5;
    const int Tree=N*400;
    int n,m,node=0,totn;
    int ql[N],qr[N],op[N],b[N],k[N];
    int rt[N<<2],tag[Tree];
    ll sz[Tree];
    struct Tnode{int L,R;}T[Tree];
    inline int read(){
        int x=0,f=1;char ch=getchar();
        while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
        while ('0'<=ch && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
        return x*f;
    }
    #define lc p<<1
    #define rc p<<1|1
    inline void pushdown(int p,int l,int r){
        int &v=tag[p],mid=(l+r)>>1;
        if (!T[p].L)T[p].L=++node;
        if (!T[p].R)T[p].R=++node;
        tag[T[p].L]+=v,tag[T[p].R]+=v;
        sz[T[p].L]+=v*(mid-l+1),sz[T[p].R]+=v*(r-mid);
        v=0;
    }
    
    inline void update(int &p,int ql,int qr,int l=1,int r=n){
        if (!p)p=++node;
        if (ql<=l && r<=qr){
            ++tag[p];sz[p]+=r-l+1;
            return;
        }
        if (tag[p])pushdown(p,l,r);
        rint mid=(l+r)>>1;
        if (ql<=mid) update(T[p].L,ql,qr,l,mid);
        if (mid<qr) update(T[p].R,ql,qr,mid+1,r);
        sz[p]=sz[T[p].L]+sz[T[p].R];
    }
    inline void add(int ql,int qr,int k,int p=1,int l=1,int r=totn){
        update(rt[p],ql,qr);
        if (l==r) return;
        rint mid=(l+r)>>1;
        if (k<=mid) add(ql,qr,k,lc,l,mid);
            else add(ql,qr,k,rc,mid+1,r);
    }
    
    inline ll getsum(int &p,int ql,int qr,int l=1,int r=n){
        if (!p)return 0;
        if (ql<=l && r<=qr) return sz[p];
        if (tag[p])pushdown(p,l,r);
        rint mid=(l+r)>>1;
        ll tt=0;
        if (ql<=mid) tt+=getsum(T[p].L,ql,qr,l,mid);
        if (mid<qr) tt+=getsum(T[p].R,ql,qr,mid+1,r);
        return tt;
    }
    inline int query(int ql,int qr,ll k,int p=1,int l=1,int r=totn){
        if (l==r) return b[l];
        rint mid=(l+r)>>1;
        ll tt=getsum(rt[rc],ql,qr);
        if (tt<k) return query(ql,qr,k-tt,lc,l,mid);
            else return query(ql,qr,k,rc,mid+1,r);
    }
    int main(){
        n=read(),m=read();
        for (rint i=1;i<=m;++i){
            op[i]=read(),ql[i]=read(),qr[i]=read(),k[i]=read();
            if (op[i]==1)b[++totn]=k[i];
        }
        sort(b+1,b+totn+1);
        totn=unique(b+1,b+totn+1)-b-1;
        for (rint i=1;i<=m;++i)
            if (op[i]==1)k[i]=lower_bound(b+1,b+totn+1,k[i])-b;
        for (rint i=1;i<=m;++i){
            if (op[i]==1){
                add(ql[i],qr[i],k[i]);
            }else{
                printf("%d\n",query(ql[i],qr[i],k[i]));
            }
        }
        return 0;
    }