之前用权值线段树套区间线段树水过，现在再练习一下整体二分
原题：
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
N,M≤50000
对于每个1操作，abs（k)≤10^9
对于每个2操作，保证k≤所询问区间内数的个数的总数
这个数据是经过妹主席强化的，不过用整体二分解决的话没什么区别
整体二分这个东西呢，和cdq分治挺像的，我做得题少，也不好说出他们的区别
这题首先先按时间轴排序，其实并不用排序，输入顺序即可，第k大使用整体二分查找
具体过程呢，就是每次递归有两个范围，x,y表示时间轴，l,r表示数的范围
然后mid=(l+r)>>1，按照时间轴递增顺序，如果插入操作的值>mid就给插入操作的区间都++并分到右边，否则分到左边
查询操作就查询查询操作要查询的范围中的值（也就是这次递归中在查询区间中插入的个数），如果这个值<=查询的k，就什么也不动分到左边，否则k-=查询出的个数并分到右边
最后如果l==r，在x到y区间中的询问答案就是l
因为这里是使用两个栈来进行左右划分，设左边的栈顶为t1，左边的时间轴就被分成x,x+t1-1，右边分成x+t1,y，所以这里在每次递归开始的时候要判断x>y时直接退出
我做这道题的时候出现了一些问题：
栈当然要开全局，栈顶也可以开全局，但是进行左右划分的时候不能用全局的栈顶来划分！因为进行左边的递归，开始右边的递归的时候，范围本来应该是x+t1,y，但是这里的t1在进行左边递归的时候被改变了，这个时候就会发生问题
线段树区间修改要push_up
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
const int oo=;
struct dcd{int x,l,r,v,mk;}a[];
int n,m;
int ans[];
dcd q[][]; int hd[];
int v[],dt[];
void pshd(int x,int l,int r){
int md=(l+r)>>;
v[x<<]+=dt[x]*(md-l+),v[x<<|]+=dt[x]*(r-md);
dt[x<<]+=dt[x],dt[x<<|]+=dt[x];
dt[x]=;
}
void mdf(int x,int xx,int yy,int l,int r,int vv){
if(xx==l && yy==r){ v[x]+=vv*(r-l+),dt[x]+=vv; return ;}
pshd(x,xx,yy); int md=(xx+yy)>>;
if(l<=md && r>md) mdf(x<<,xx,md,l,md,vv),mdf(x<<|,md+,yy,md+,r,vv);
else if(r<=md) mdf(x<<,xx,md,l,r,vv);
else mdf(x<<|,md+,yy,l,r,vv);
v[x]=v[x<<]+v[x<<|];
}
int qr(int x,int xx,int yy,int l,int r){
if(xx==l && yy==r) return v[x];
pshd(x,xx,yy); int md=(xx+yy)>>;
if(l<=md && r>md) return qr(x<<,xx,md,l,md)+qr(x<<|,md+,yy,md+,r);
else if(r<=md) return qr(x<<,xx,md,l,r);
else return qr(x<<|,md+,yy,l,r);
}
void whlbnr(int x,int y,long long l,long long r){
if(x>y) return ;
if(l==r){
for(int i=x;i<=y;++i)if(a[i].mk==) ans[a[i].x]=l;
return ;
}
long long tmp,md=(l+r)>>;
hd[]=hd[]=;
for(int i=x;i<=y;++i){
if(a[i].mk==){
if(a[i].v>md) q[++hd[]][]=a[i],mdf(,,n,a[i].l,a[i].r,);
else q[++hd[]][]=a[i];
}
else{
if((tmp=qr(,,n,a[i].l,a[i].r))<a[i].v) a[i].v-=tmp,q[++hd[]][]=a[i];
else q[++hd[]][]=a[i];
}
}
for(int i=x;i<=y;++i)if(a[i].mk== && a[i].v>md) mdf(,,n,a[i].l,a[i].r,-);
for(int i=;i<hd[];++i) a[x+i]=q[i+][];
for(int i=;i<hd[];++i) a[x+hd[]+i]=q[i+][];
int t1=hd[];
whlbnr(x,x+t1-,l,md);
whlbnr(x+t1,y,md+,r);
//for(int i=x;i<=y;++i)if(a[i].mk==1 && a[i].v>((md+1+r)>>1)) mdf(1,1,n,a[i].l,a[i].r,1);
//whlbnr(x,x+hd[0]-1,l,md),whlbnr(x+hd[0],y,md+1,r);
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n>>m;
for(int i=;i<=m;++i) a[i].mk=rd(),a[i].l=rd(),a[i].r=rd(),a[i].v=rd()+(a[i].mk==?oo:),a[i].x=i;
whlbnr(,m,,oo<<);
//for(int i=1;i<=m;++i)if(a[i].mk==2) printf("%d ",a[i].v);
for(int i=;i<=m;++i)if(ans[i]) printf("%d\n",ans[i]-oo);
return ;
}