有几个点卡常数……
发现若第一维为位置，第二维为大小，那么修改时第一维修改区间，查询时第一维查询区间，必须挂标记。而这种情况下标记很抽象，而且Push_down不是O（1）的，并不可行。
那要怎么做呢？不妨交换一下，第一维为大小，第二维为位置，在第二维中挂标记，这样Push_down就是O（1）的了。
做完这道题，我最大的启发就是：树套树不适于在第一维挂标记，因为标记的维度会是一维的，根本不好维护。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>
using namespace std;
const int maxn=;
const int maxm=;
int rt[maxn*],tot,n,m;
int ch[maxm][],sum[maxm],tag[maxm]; void Push_up(int x){
sum[x]=sum[ch[x][]]+sum[ch[x][]];
} void Add(int &x,int l,int r,int d){
if(!x)x=++tot;
sum[x]+=(r-l+)*d;
tag[x]+=d;
} void Push_down(int x,int l,int r){
if(tag[x]&&l!=r){
int mid=(l+r)>>;
if(!ch[x][])ch[x][]=++tot;
if(!ch[x][])ch[x][]=++tot;
sum[ch[x][]]+=(mid-l+)*tag[x];tag[ch[x][]]+=tag[x];
sum[ch[x][]]+=(r-mid)*tag[x];tag[ch[x][]]+=tag[x];
tag[x]=;
}
} void Update(int &x,int l,int r,int a,int b){
if(!x)x=++tot;
Push_down(x,l,r);
if(l>=a&&r<=b){sum[x]+=r-l+;tag[x]+=;return;}
int mid=(l+r)>>;
if(mid>=a)Update(ch[x][],l,mid,a,b);
if(mid<b)Update(ch[x][],mid+,r,a,b);
Push_up(x);
} void Modify(int x,int l,int r,int g,int a,int b){
Update(rt[x],,n,a,b);
if(l==r)return;
int mid=(l+r)>>;
if(mid>=g)Modify(x<<,l,mid,g,a,b);
else Modify(x<<|,mid+,r,g,a,b);
} int Query(int x,int l,int r,int a,int b){
if(!x)return ;
Push_down(x,l,r);
if(l>=a&&r<=b)return sum[x];
int mid=(l+r)>>,ret=;
if(mid>=a)ret=Query(ch[x][],l,mid,a,b);
if(mid<b)ret+=Query(ch[x][],mid+,r,a,b);
return ret;
} int Solve(int l,int r,int k){
int lo=,hi=n,p=;
while(lo<hi){
int mid=(lo+hi)>>,tmp;
tmp=Query(rt[p<<],,n,l,r);
if(tmp>=k)hi=mid,p<<=;
else lo=mid+,p=p<<|,k-=tmp;
}
return hi;
} int op,a,b,c;
int main(){
#ifndef ONLINE_JUDGE
freopen("zjoi13_sequence.in","r",stdin);
freopen("zjoi13_sequence.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d%d%d",&op,&a,&b,&c);
if(op==)Modify(,,n,n-c+,a,b);
else printf("%d\n",n-Solve(a,b,c)+);
}
//printf("%.2f\n",(double)clock()/CLOCKS_PER_SEC);
return ;
}
然后就是喜闻乐见的整体二分，很好理解。
有些地方没有缩行，打丑了，理论上60行足矣，这就是整体二分的威力！
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
struct Node{
int tp,l,r,k,id,tmp;
}p[maxn],tmp[maxn]; int b0[maxn],b1[maxn];
int v0[maxn],v1[maxn];
int ans[maxn],n,Q,tim,cntQ; void Add0(int x,int d){
while(x<=n){
b0[x]=v0[x]==tim?b0[x]+d:d;
v0[x]=tim;
x+=x&(-x);
}
} void Add1(int x,int d){
while(x<=n){
b1[x]=v1[x]==tim?b1[x]+d:d;
v1[x]=tim;
x+=x&(-x);
}
} void Update(int l,int r,int d){
Add0(l,d);
Add0(r+,-d);
Add1(l,-(l-)*d);
Add1(r+,r*d);
} int Query(int x){
int ret=;
for(int i=x;i;i-=i&(-i))
ret+=v0[i]==tim?b0[i]:;
ret*=x;
for(int i=x;i;i-=i&(-i))
ret+=v1[i]==tim?b1[i]:;
return ret;
} int Que(int l,int r){
return Query(r)-Query(l-);
} void Solve(int h,int t,int l,int r){
if(h>t)return;
if(l==r){
for(int i=h;i<=t;i++)
ans[p[i].id]=l;
return;
}
int mid=(l+r)>>;
int ct1=h,ct2=h;++tim;
for(int i=h;i<=t;i++){
if(p[i].tp==){
if(p[i].k>mid)continue;
Update(p[i].l,p[i].r,);
ct2+=;
}
else{
p[i].tmp=Que(p[i].l,p[i].r);
if(p[i].tmp>=p[i].k)ct2+=;
}
}
for(int i=h;i<=t;i++){
if(p[i].tp==){
if(p[i].k>mid)tmp[ct2++]=p[i];
else tmp[ct1++]=p[i];
}
else{
if(p[i].tmp>=p[i].k)tmp[ct1++]=p[i];
else p[i].k-=p[i].tmp,tmp[ct2++]=p[i];
}
}
for(int i=h;i<=t;i++)p[i]=tmp[i];
Solve(h,ct1-,l,mid);Solve(ct1,t,mid+,r);
} int main(){
#ifndef ONLINE_JUDGE
freopen("zjoi13_sequence.in","r",stdin);
freopen("zjoi13_sequence.out","w",stdout);
#endif
scanf("%d%d",&n,&Q);
for(int i=;i<=Q;i++){
scanf("%d%d",&p[i].tp,&p[i].l);
scanf("%d%d",&p[i].r,&p[i].k);
if(p[i].tp==){
p[i].id=++cntQ;
p[i].k=Que(p[i].l,p[i].r)-p[i].k+;
}
else
Update(p[i].l,p[i].r,);
} Solve(,Q,,n); for(int i=;i<=cntQ;i++)
printf("%d\n",ans[i]);
return ;
}