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
|
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
using namespace std;
const int N=1e5;
int rt[N<<2],lz[N<<2],n,m,T;
inline void (int o){rt[o]=rt[o<<1]+rt[o<<1|1];}
inline void pushdown(int o,int len){
if(lz[o]==-1)return ;
lz[o<<1]=lz[o<<1|1]=lz[o];
if(!lz[o]){
rt[o<<1]=len-(len>>1);
rt[o<<1|1]=len>>1;
}
else rt[o<<1]=rt[o<<1|1]=0;;
lz[o]=-1;
}
inline void build(int o,int l,int r){
lz[o]=-1;
if(l==r){rt[o]=1;return ;}
int mid=l+r>>1;
build(lson);
build(rson);
pushup(o);
}
inline void update(int o,int l,int r,int L,int R){
if(L<=l&&R>=r){rt[o]=0;lz[o]=1;return ;}
pushdown(o,r-l+1);
int mid=l+r>>1;
if(L<=mid)update(lson,L,R);
if(R>mid)update(rson,L,R);
pushup(o);
}
inline int clear(int o,int l,int r,int L,int R){
if(L<=l&&R>=r){lz[o]=0;int t=rt[o];rt[o]=r-l+1;return rt[o]-t;}
pushdown(o,r-l+1);
int mid=l+r>>1,ans=0;
if(L<=mid)ans+=clear(lson,L,R);
if(R>mid)ans+=clear(rson,L,R);
pushup(o);
return ans;
}
inline int query(int o,int l,int r,int L,int R){
if(L>r||R<l)return 0;
if(L<=l&&R>=r)return rt[o];
pushdown(o,r-l+1);
int mid=l+r>>1,ans=0;
if(L<=mid)ans+=query(lson,L,R);
if(R>mid)ans+=query(rson,L,R);
return ans;
}
inline int ask(int o,int l,int r,int L,int R,int x){
if(l==r)return l;
pushdown(o,r-l+1);
int mid=l+r>>1;
int t=query(lson,L,R);
if(x<=t)return ask(lson,L,R,x);
else return ask(rson,L,R,x-t);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--){
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1){
int t=query(1,1,n,l+1,n);
if(!t)puts("Can not put any one.");
else {
l=ask(1,1,n,l+1,n,1);
r=ask(1,1,n,l,n,min(t,r));
printf("%d %dn",l-1,r-1);
update(1,1,n,l,r);
}
}
else printf("%dn",clear(1,1,n,l+1,r+1));
}
printf("n");
}
return 0;
}
|
近期评论