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;
}