#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> #include <set> #include <map> #include <vector> #include <queue> #include <string> #include <math.h> using namespace std; const int MAXN = 50010; struct Node { //1表示空的 //0表示有花 int l,r; //和 int sum; //如果是1 ，表示没花 //如果是-1，表示有花 //初始化为0 int lazy; //区间最左边的1 int first; //区间最右边的1 int last; }segTree[MAXN*3]; void push_up(int i) { if(segTree[i].l==segTree[i].r) return; segTree[i].sum = segTree[i<<1].sum+segTree[(i<<1)|1].sum; //如果左区间不是-1，表示左区间没花 ，那么first就是左区间的first if(segTree[i<<1].first != -1) segTree[i].first = segTree[i<<1].first; else //那就是右区间的 segTree[i].first = segTree[(i<<1)|1].first; //如果右区间不是-1，表示右区间没花，那么last就是右区间的last if(segTree[(i<<1)|1].last != -1) segTree[i].last = segTree[(i<<1)|1].last; else //那就是左区间的 segTree[i].last = segTree[(i<<1)].last; } void push_down(int i) { //如果已经到叶节点，就不能往下递归 if(segTree[i].r == segTree[i].l) return; //如果当前区间懒标记为1 ，没有花 if(segTree[i].lazy==1) { //最左边的1就是左端点 segTree[i<<1].first = segTree[i<<1].l; //最右边的0就是右端点 segTree[i<<1].last = segTree[i<<1].r; //和 segTree[i<<1].sum = segTree[i<<1].r-segTree[i<<1].l+1; //左区间懒标记，1表示没花 segTree[i<<1].lazy=1; segTree[(i<<1)|1].first = segTree[(i<<1)|1].l; segTree[(i<<1)|1].last = segTree[(i<<1)|1].r; segTree[(i<<1)|1].sum = segTree[(i<<1)|1].r-segTree[(i<<1)|1].l+1; segTree[(i<<1)|1].lazy=1; } //如果没有花 ，有花 if(segTree[i].lazy == -1) { //有花 //那么就没有 segTree[i<<1].first = -1; segTree[i<<1].last = -1; segTree[i<<1].sum = 0; segTree[i<<1].lazy=-1; segTree[(i<<1)|1].first = -1; segTree[(i<<1)|1].last = -1; segTree[(i<<1)|1].sum = 0; segTree[(i<<1)|1].lazy=-1; } //懒标记清空 segTree[i].lazy = 0; } //初始化 void build(int i,int l,int r) { // segTree[i].l = l; segTree[i].r = r; //1的个数 segTree[i].sum = r-l+1; segTree[i].lazy = 0; //最左端的1 segTree[i].first = l; //最右端的1 segTree[i].last = r; if(l==r) return ; int mid = (l+r)/2; build(i<<1,l,mid); build((i<<1)|1,mid+1,r); } void update(int i,int l,int r,int type) { if(segTree[i].l == l && segTree[i].r==r) { //如果是插花 if(type == 0) { if(segTree[i].sum == 0) return; segTree[i].sum = 0; segTree[i].lazy = -1; segTree[i].first = -1; segTree[i].last = -1; return; } //如果是清空 ，都赋值为1 else if(type == 1) { if(segTree[i].sum == segTree[i].r-segTree[i].l+1) return; segTree[i].sum = segTree[i].r-segTree[i].l+1; segTree[i].lazy = 1; segTree[i].first = segTree[i].l; segTree[i].last = segTree[i].r; return; } } push_down(i); int mid = (segTree[i].l + segTree[i].r)/2; if(r <= mid) update(i<<1,l,r,type); else if(l > mid) update((i<<1)|1,l,r,type); else { update(i<<1,l,mid,type); update((i<<1)|1,mid+1,r,type); } push_up(i); } int sum(int i,int l,int r) { if(segTree[i].l == l && segTree[i].r == r) { return segTree[i].sum; } push_down(i); int mid = (segTree[i].l + segTree[i].r)/2; if(r <= mid) return sum(i<<1,l,r); else if(l > mid) return sum((i<<1)|1,l,r); else return sum((i<<1)|1,mid+1,r)+sum(i<<1,l,mid); } int n,m; int query1(int i,int l,int r) { if(segTree[i].l == l && segTree[i].r == r) { return segTree[i].first; } push_down(i); int mid = (segTree[i].l + segTree[i].r)/2; int ans1,ans2; if(r <= mid) return query1(i<<1,l,r); else if(l > mid) return query1((i<<1)|1,l,r); else { ans1 = query1(i<<1,l,mid); if(ans1 != -1) return ans1; return query1((i<<1)|1,mid+1,r); } } int query2(int i,int l,int r) { if(segTree[i].l == l && segTree[i].r == r) { return segTree[i].last; } push_down(i); int mid = (segTree[i].l + segTree[i].r)/2; int ans1,ans2; if(r <= mid) return query2(i<<1,l,r); else if(l > mid) return query2((i<<1)|1,l,r); else { ans1 = query2((i<<1)|1,mid+1,r); if(ans1 != -1) return ans1; return query2(i<<1,l,mid); } } int judge(int A,int F) { //如果不能再放了 if(sum(1,A,n)==0) return -1; if(sum(1,A,n)<F) return n; int l= A,r = n; int ans=A; while(l<=r) { int mid = (l+r)/2; if(sum(1,A,mid)>=F) { ans = mid; r = mid-1; } else l = mid+1; } return ans; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); build(1,1,n); int op,u,v; while(m--) { scanf("%d%d%d",&op,&u,&v); if(op == 1) { u++; int t = judge(u,v); if(t==-1) { printf("Can not put any one. "); continue; } //插花的起点、终点 printf("%d %d ",query1(1,u,t)-1,query2(1,u,t)-1); update(1,u,t,0); } else { u++;v++; // 区间长度-剩下的1 printf("%d ",v-u+1-sum(1,u,v)); update(1,u,v,1); } } printf(" "); } return 0; }