1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 typedef pair <int,int> pII; typedef long long ll; const int INF = 0x3f3f3f3f;
const int maxn = 5e5 + 10; int m,n,T; int now,ed,st; bool flag = 0; int sum[maxn<<2],lazy[maxn<<2]; void pushup(int rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void pushdown(int rt,int len){ if(lazy[rt] == 0){ lazy[rt<<1] = lazy[rt<<1|1] = 0; sum[rt<<1] = sum[rt<<1|1] = 0; lazy[rt] = -1; } if(lazy[rt] == 1){ lazy[rt<<1] = lazy[rt<<1|1] = 1; sum[rt<<1] = len-len/2; sum[rt<<1|1] = len/2; lazy[rt] = -1; } } void build(int l,int r,int rt){ lazy[rt] = -1; if(l==r){ sum[rt] = 0; return ; } int mid = l+r>>1; build(lson);build(rson); pushup(rt); } void update(int p,int l,int r,int rt){ if(now == 0) return; if(r-l+1 == sum[rt]) return; if(sum[rt] == 0 && now >= r-l+1 && l>=p){ sum[rt] = r-l+1; now -= (r-l+1); lazy[rt] = 1; if(!flag) st = l,flag = 1,ed = r; else ed = r; return; } pushdown(rt,r-l+1); int mid = l+r>>1; if(p <= mid) update(p,lson); update(p,rson); pushup(rt); } void update(int L,int R,int l,int r,int rt){ if(L<=l && r<=R){ now += sum[rt]; sum[rt] = 0; lazy[rt] = 0; return; } pushdown(rt,r-l+1); int mid = l+r>>1; if(L <= mid) update(L,R,lson); if(mid < R) update(L,R,rson); pushup(rt); } int main(){ #ifdef LOCAL freopen("1.in","r",stdin); #endif scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); build(1,n,1); rep(i,0,m){ int op,a,b; scanf("%d%d%d",&op,&a,&b); if(op==1){ a++; now = b;st = ed = a; flag = 0; update(a,1,n,1); if(now==b){ puts("Can not put any one."); }else{ ed--;st--; printf("%d %d\n",st,ed); } }else{ now = 0; a++;b++; update(a,b,1,n,1); printf("%d\n",now); } } puts(""); } return 0; }
|