在二分的基础上进行线段树。
cl[i]:i区间的长度
flag[i]:i区间的标记flag[i]==1,i区间为有花。flag[i]==2,i区间没有花。
1 a b：
从a开始，插b朵花。
第一次二分，二分出开始插花的点。
第二次二分，二分出结束插花的点。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stack>
using namespace std;
#define INF 99999999
#define lmin 1
#define rmax n
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root lmin,rmax,1
#define maxn 55000
int cl[maxn*4];
int flag[maxn*4];
void push_up(int rt)
{cl[rt]=cl[rt<<1]+cl[rt<<1|1];
}
void push_down(int rt)
{
}
void creat(int l,int r,int rt)
{cl[rt]=0;flag[rt]=0;if(l!=r){creat(lson);creat(rson);}
}
void update(int ll,int rr,int x,int l,int r,int rt)
{if(r<ll||l>rr)return ;if(ll<=l&&rr>=r){if(x)cl[rt]=r-l+1;else cl[rt]=0;flag[rt]=x+1;return ;}if(flag[rt]){flag[rt<<1]=flag[rt<<1|1]=flag[rt];cl[rt<<1]=(l+r)/2-l+1;cl[rt<<1|1]=r-(l+r)/2;if(flag[rt]==1)cl[rt<<1]=cl[rt<<1|1]=0;flag[rt]=0;}update(ll,rr,x,lson);update(ll,rr,x,rson);push_up(rt);
}
int query(int ll,int rr,int l,int r,int rt)
{if(rr<l||ll>r)return 0;if(ll<=l&&rr>=r){//cout<<l<<" "<<r<<" "<<cl[rt]<<endl;return cl[rt];}if(flag[rt]){flag[rt<<1]=flag[rt<<1|1]=flag[rt];cl[rt<<1]=(l+r)/2-l+1;cl[rt<<1|1]=r-(l+r)/2;if(flag[rt]==1)cl[rt<<1]=cl[rt<<1|1]=0;flag[rt]=0;}return query(ll,rr,lson)+query(ll,rr,rson);
}
int main()
{int cas,T;int n,m;int l,r,mid;int k,a,b,c;int m1,m2;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);creat(root);while(m--){scanf("%d%d%d",&k,&a,&b);a++;b++;if(k==1){b--;int x=query(a,n,root);if(x==n-a+1){cout<<"Can not put any one."<<endl;continue;}b=min(b,n-a+1-x);l=a;r=n+1;mid=(l+r)/2;while(l<r){if(query(a,mid,root)<mid-a+1)r=mid;else l=mid+1;mid=(l+r)/2;}m1=mid;l=m1;r=n+1;mid=(l+r)/2;while(l<r){if(mid-m1+1-query(m1,mid,root)>=b)r=mid;else l=mid+1;mid=(l+r)/2;}m2=mid;if(m2>n)m2=n;update(m1,m2,1,root);printf("%d %d\n",m1-1,m2-1);}else{printf("%d\n",query(a,b,root));update(a,b,0,root);}}puts("");}return 0;
}