喜闻乐见的简单树套树= =第一维按权值建树状数组，第二维按下标建动态开点线段树，修改相当于第二维区间加，查询在树状数组上二分，比一般的线段树还短= =可惜并不能跑过整体二分= =另外bzoj上的数据有负数= =其他树套树方法也是可以的爱怎么套怎么套= =
#include<cstdio>
#define J (i+j>>1)
#define I (J+1)
typedef unsigned ll;
const int N=1e5+5;
ll n,m,q,i,j,k,s,t,u,v;
struct node{
ll s,t;
node*i,*j;
}e[N*320];
node*a=e,*r[N];
void vary(node*&o,int s,int t,int i=1,int j=n){
if(!o)o=a++;
o->s+=t-s+1;
if(s==i&&t==j)++o->t;
else if(t<I)
vary(o->i,s,t,i,J);
else if(s>J)
vary(o->j,s,t,I,j);
else{
vary(o->i,s,J,i,J);
vary(o->j,I,t,I,j);
}
}
void ask(node*o,int s,int t,int i=1,int j=n){
if(!o)return;
if(s==i&&t==j)u+=o->s;
else{
u+=o->t*(t-s+1);
if(t<I)
ask(o->i,s,t,i,J);
else if(s>J)
ask(o->j,s,t,I,j);
else{
ask(o->i,s,J,i,J);
ask(o->j,I,t,I,j);
}
}
}
int main(){
scanf("%d%d",&n,&q);
m=n<<1^1;
while(q--){
scanf("%d%d%d%d",&j,&s,&t,&k);
if(j==2){
for(i=65536,v=j=0;i;i>>=1)
if(j+i<=m){
u=0,ask(r[j+i],s,t);
if(v+u<k)
j+=i,v+=u;
}
printf("%d\n",n-j);
}else
for(i=n-k+1;i<=m;i+=i&-i)
vary(r[i],s,t);
}
}