Alice is so popular that she can receive many flowers everyday. She has N vases numbered from 0 to N-1. When she receive some flowers, she will try to put them in the vases, one flower in one vase. She randomly choose the vase A and try to put a flower in the vase. If the there is no flower in the vase, she will put a flower in it, otherwise she skip this vase. And then she will try put in the vase A+1, A+2, ..., N-1, until there is no flower left or she has tried the vase N-1. The left flowers will be discarded. Of course, sometimes she will clean the vases. Because there are too many vases, she randomly choose to clean the vases numbered from A to B(A <= B). The flowers in the cleaned vases will be discarded.
题意：有 0~n-1 共 n 个花瓶，一个花瓶可以插一束花，现在有两个操作，一个是从 A 号花瓶开始插 k 束花，若花瓶有花就顺延到下一个花瓶，直到插完 k 束花或插完 n-1 号花瓶，问她插的第一个和最后一个花瓶编号。第二个操作是清空一段区间的花，问共丢掉多少花。
线段树保存区间空瓶数、首个空瓶和末个空瓶。树上二分查找 k 个空瓶，并更新最大最小空瓶位置。区间清除。
#include<stdio.h>
#include<string.h>
const int maxm=;
const int INF=0x3f3f3f3f; int st[maxm<<],ma[maxm<<],mi[maxm<<];
int ch[maxm<<];
int maxx,minn,k; inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;} void build(int o,int l,int r){
ma[o]=r;
mi[o]=l;
st[o]=r-l+;
ch[o]=;
if(l==r)return;
int m=l+((r-l)>>);
build(o<<,l,m);
build(o<<|,m+,r);
} void pushdown(int o,int l,int r){
if(ch[o]==){
ch[o<<]=ch[o<<|]=;
int m=l+((r-l)>>);
st[o<<]=st[o<<|]=;
ma[o<<]=ma[o<<|]=-;
mi[o<<]=mi[o<<|]=INF;
ch[o]=;
}
else if(ch[o]==){
ch[o<<]=ch[o<<|]=;
int m=l+((r-l)>>);
st[o<<]=m-l+;
st[o<<|]=r-m;
ma[o<<]=m;
ma[o<<|]=r;
mi[o<<]=l;
mi[o<<|]=m+;
ch[o]=;
}
} void update1(int o,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r){
if(k>=st[o]){
k-=st[o];
maxx=max(maxx,ma[o]);
minn=min(minn,mi[o]);
ma[o]=-;
mi[o]=INF;
st[o]=;
ch[o]=;
return;
}
else if(l==r)return;
}
pushdown(o,l,r);
int m=l+((r-l)>>);
if(ql<=m&&k)update1(o<<,l,m,ql,qr);
if(qr>=m+&&k)update1(o<<|,m+,r,ql,qr);
ma[o]=max(ma[o<<],ma[o<<|]);
mi[o]=min(mi[o<<],mi[o<<|]);
st[o]=st[o<<]+st[o<<|];
} int update2(int o,int l,int r,int ql,int qr){
if(ql<=l&&qr>=r){
int ans=r-l+-st[o];
st[o]=r-l+;
ma[o]=r;
mi[o]=l;
ch[o]=;
return ans;
}
pushdown(o,l,r);
int m=l+((r-l)>>);
int ans=;
if(ql<=m)ans+=update2(o<<,l,m,ql,qr);
if(qr>=m+)ans+=update2(o<<|,m+,r,ql,qr);
ma[o]=max(ma[o<<],ma[o<<|]);
mi[o]=min(mi[o<<],mi[o<<|]);
st[o]=st[o<<]+st[o<<|];
return ans;
} int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
build(,,n-);
for(int i=;i<=m;++i){
int t;
scanf("%d",&t);
if(t==){
int a;
scanf("%d%d",&a,&k);
maxx=-;
minn=INF;
update1(,,n-,a,n-);
if(maxx==-&&minn==INF)printf("Can not put any one.\n");
else printf("%d %d\n",minn,maxx);
}
else if(t==){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",update2(,,n-,a,b));
}
}
printf("\n");
}
return ;
}