hdu4553[线段树维护连续区间]

发表于 | 分类于 ， ， | 阅读数 次

链接:hdu4553[线段树维护连续区间]

题解

  • poj3667升级版,注意更新顺序
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
#include<iostream>
#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 lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
using namespace std;
const int N=1e6+7;
int llen[2][N<<2],rlen[2][N<<2],mlen[2][N<<2],lz[2][N<<2],n,m,T,a,b;
char op[10];
inline void pushup(int o,int len ,int t){
	llen[t][o]=llen[t][o<<1];rlen[t][o]=rlen[t][o<<1|1];
	if(llen[t][o]==len-(len>>1))llen[t][o]+=llen[t][o<<1|1];
	if(rlen[t][o]==len>>1)rlen[t][o]+=rlen[t][o<<1];
	mlen[t][o]=max(max(mlen[t][o<<1],mlen[t][o<<1|1]),rlen[t][o<<1]+llen[t][o<<1|1]);
}
inline void pushdown(int o,int len,int t){
	if(lz[t][o]==-1)return ;
	lz[t][o<<1]=lz[t][o<<1|1]=lz[t][o];
	llen[t][o<<1]=rlen[t][o<<1]=mlen[t][o<<1]=lz[t][o]?len-(len>>1):0;
	llen[t][o<<1|1]=rlen[t][o<<1|1]=mlen[t][o<<1|1]=lz[t][o]?len>>1:0;
	lz[t][o]=-1;
}
inline void build(int o,int l,int r){
	rep(t,0,1)llen[t][o]=rlen[t][o]=mlen[t][o]=r-l+1,lz[t][o]=-1;
	if(l==r)return ;
	int mid=l+r>>1;
	build(lson);
	build(rson);
}
inline void update(int o,int l,int r,int L,int R,int x,int t){
	if(L<=l&&R>=r){
		llen[t][o]=rlen[t][o]=mlen[t][o]=x?(r-l+1):0;
		lz[t][o]=x;
		return ;
	}
	pushdown(o,r-l+1,t);
	int mid=l+r>>1;
	if(L<=mid)update(lson,L,R,x,t);
	if(R>mid)update(rson,L,R,x,t);
	pushup(o,r-l+1,t);
}
inline int query(int o,int l,int r,int L,int R,int x,int t){
	if(L==R)return L;
	pushdown(o,r-l+1,t);
	int mid=l+r>>1;
	if(mlen[t][o<<1]>=x)return query(lson,L,mid,x,t);
	if(rlen[t][o<<1]+llen[t][o<<1|1]>=x)return mid-rlen[t][o<<1]+1;
	return query(rson,mid+1,R,x,t);
}
int main(){
	scanf("%d",&T);
	rep(k,1,T){
		printf("Case %d:\n",k);
		scanf("%d%d",&n,&m);
		build(1,1,n);
		while(m--){
			scanf("%s",op);
			if(op[0]=='D'){
				scanf("%d",&a);
				if(mlen[0][1]>=a){
					printf("%d,let's fly\n",b=query(1,1,n,1,n,a,0));
					update(1,1,n,b,b+a-1,0,0);
				}
				else puts("fly with yourself");
			}
			else if(op[0]=='N'){
				scanf("%d",&a);
				if(mlen[0][1]>=a){
					printf("%d,don't put my gezi\n",b=query(1,1,n,1,n,a,0));
					update(1,1,n,b,b+a-1,0,0);
					update(1,1,n,b,b+a-1,0,1);
				}
				else if(mlen[1][1]>=a){
					printf("%d,don't put my gezi\n",b=query(1,1,n,1,n,a,1));
					update(1,1,n,b,b+a-1,0,0);
					update(1,1,n,b,b+a-1,0,1);
				
				}
				else puts("wait for me");
			}
			else {
				scanf("%d%d",&a,&b);
				update(1,1,n,a,b,1,0);
				update(1,1,n,a,b,1,1);
				puts("I am the hope of chinese chengxuyuan!!");
			}
		}
	}
	return 0;
}