Description：

给定一个序列，支持两种操作

1.在[L,R]的每个位置上加上一个数 （注意一个位置上有多个数）

2.查询[L,R]上所有数中的第K大

Hint:

\(n,m<=5e4\)

Solution:

一道很好的整体二分题，在值域上二分所有询问的答案，并在线段树上维护\(size\)

详见代码

#include<bits/stdc++.h>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

const int mxn=5e4+5;

struct Q {

    int opt,l,r,x,id;

}q[mxn],tl[mxn],tr[mxn];

int n,m,tot;

ll ans[mxn],t[mxn<<2],rec[mxn<<2],tag[mxn<<2];

namespace SegmentTree {

    inline void push_up(int p) {

        t[p]=t[ls]+t[rs];

    };

    inline void push_down(int l,int r,int p) {

        if(rec[p]) {

            tag[ls]=tag[rs]=t[ls]=t[rs]=0;

            rec[ls]=rec[rs]=1;

            rec[p]=0;

        }

        if(tag[p]) {

            int mid=(l+r)>>1;

            tag[ls]+=tag[p],tag[rs]+=tag[p];

            t[ls]+=(mid-l+1)*tag[p],

            t[rs]+=(r-mid)*tag[p];

            tag[p]=0;

        }

    };

    void update(int l,int r,int ql,int qr,int val,int p)	{

        if(ql<=l&&r<=qr) {

            t[p]+=(r-l+1)*val;

            tag[p]+=val;

            return ;

        }

        int mid=(l+r)>>1; push_down(l,r,p);

        if(ql<=mid) update(l,mid,ql,qr,val,ls);

        if(qr>mid) update(mid+1,r,ql,qr,val,rs);

        push_up(p);

    };

    ll query(int l,int r,int ql,int qr,int p) {

        if(ql<=l&&r<=qr) return t[p]; ll res=0;

        int mid=(l+r)>>1; push_down(l,r,p);

        if(ql<=mid) res+=query(l,mid,ql,qr,ls);

        if(qr>mid) res+=query(mid+1,r,ql,qr,rs);

        return res;

    };

}

using namespace SegmentTree;

int ss;

void solve(int l,int r,int ql,int qr)

{

    if(l==r) {

        for(int i=ql;i<=qr;++i)

            if(q[i].opt==2)

                if(!ans[q[i].id]) ans[q[i].id]=l;

        return ;

    }

    int mid=(l+r)>>1,fl=0,fr=0;

    int L=0,R=0;rec[1]=1,tag[1]=t[1]=0; //有些变量不能开全局，切记！！！

    for(int i=ql;i<=qr;++i) {

        if(q[i].opt==1) {

            if(q[i].x>mid) {

                update(1,n,q[i].l,q[i].r,1,1);

                tr[++R]=q[i];

            }

            else tl[++L]=q[i];

        }

        else {

            ll tp=query(1,n,q[i].l,q[i].r,1);

            if(q[i].x<=tp) tr[++R]=q[i],fr=1;

            else q[i].x-=tp,tl[++L]=q[i],fl=1;

        }

    }

        for(int i=1;i<=L;++i) q[ql+i-1]=tl[i];

        for(int i=L+1;i<=L+R;++i) q[ql+i-1]=tr[i-L];

        if(fl) solve(l,mid,ql,ql+L-1);

        if(fr) solve(mid+1,r,ql+L,qr);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;++i) {

        scanf("%d%d%d%d",&q[i].opt,&q[i].l,&q[i].r,&q[i].x);

        if(q[i].opt==2) q[i].id=++tot;

    }

    solve(-n,n,1,m);

    for(int i=1;i<=tot;++i) printf("%lld\n",ans[i]);

    return 0;

}