之前用权值线段树套区间线段树水过，现在再练习一下整体二分

原题：

有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

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 int rd(){ int z=0,mk=1; char ch=getchar(); 9 while(ch<'0'||ch>'9'){ if(ch=='-')mk=-1; ch=getchar();}10 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();}11 return z*mk;12 }13 const int oo=1000000000;14 struct dcd{ int x,l,r,v,mk;}a[51000];15 int n,m;16 int ans[51000];17 dcd q[51000][2]; int hd[2];18 int v[810000],dt[810000];19 void pshd(int x,int l,int r){20 int md=(l+r)>>1;21 v[x<<1]+=dt[x]*(md-l+1),v[x<<1|1]+=dt[x]*(r-md);22 dt[x<<1]+=dt[x],dt[x<<1|1]+=dt[x];23 dt[x]=0;24 }25 void mdf(int x,int xx,int yy,int l,int r,int vv){26 if(xx==l && yy==r){ v[x]+=vv*(r-l+1),dt[x]+=vv; return ;}27 pshd(x,xx,yy); int md=(xx+yy)>>1;28 if(l<=md && r>md) mdf(x<<1,xx,md,l,md,vv),mdf(x<<1|1,md+1,yy,md+1,r,vv);29 else if(r<=md) mdf(x<<1,xx,md,l,r,vv);30 else mdf(x<<1|1,md+1,yy,l,r,vv);31 v[x]=v[x<<1]+v[x<<1|1];32 }33 int qr(int x,int xx,int yy,int l,int r){34 if(xx==l && yy==r) return v[x];35 pshd(x,xx,yy); int md=(xx+yy)>>1;36 if(l<=md && r>md) return qr(x<<1,xx,md,l,md)+qr(x<<1|1,md+1,yy,md+1,r);37 else if(r<=md) return qr(x<<1,xx,md,l,r);38 else return qr(x<<1|1,md+1,yy,l,r);39 }40 void whlbnr(int x,int y,long long l,long long r){41 if(x>y) return ;42 if(l==r){43 for(int i=x;i<=y;++i)if(a[i].mk==2) ans[a[i].x]=l;44 return ;45 }46 long long tmp,md=(l+r)>>1;47 hd[0]=hd[1]=0;48 for(int i=x;i<=y;++i){49 if(a[i].mk==1){50 if(a[i].v>md) q[++hd[1]][1]=a[i],mdf(1,1,n,a[i].l,a[i].r,1);51 else q[++hd[0]][0]=a[i];52 }53 else{54 if((tmp=qr(1,1,n,a[i].l,a[i].r))
            
             md) mdf(1,1,n,a[i].l,a[i].r,-1);59 for(int i=0;i
             
              ((md+1+r)>>1)) mdf(1,1,n,a[i].l,a[i].r,1);65 //whlbnr(x,x+hd[0]-1,l,md),whlbnr(x+hd[0],y,md+1,r);66 }67 int main(){ //freopen("ddd.in","r",stdin);68 cin>>n>>m;69 for(int i=1;i<=m;++i) a[i].mk=rd(),a[i].l=rd(),a[i].r=rd(),a[i].v=rd()+(a[i].mk==1?oo:0),a[i].x=i;70 whlbnr(1,m,0,oo<<1);71 //for(int i=1;i<=m;++i)if(a[i].mk==2) printf("%d ",a[i].v);72 for(int i=1;i<=m;++i)if(ans[i]) printf("%d\n",ans[i]-oo);73 return 0;74 }