UESTC 1546 Bracket Sequence

本文从WordPress迁移而来, 查看全部WordPress迁移文章

记录的信息：sum，区间和，Min，最小前缀和，Max，最大前缀和

需要3个标记来记录区间被进行过什么操作

lazy，置左，__lazy,置右，lazyr，取反

任意时刻一个区间只有一个标记能为true，可以3个均为false

置左和置右操作都简单，要维护sum，Min，Max也简单

难的是取反，这里需要用数学思维想想

取反后,Min = -Max, Max = -Min

对于一个区间，要同时满足sum = 0,Min >= 0(更苛刻点可以说是0)

一旦Min < 0，或者sum != 0，都是匹配失败的

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

char str[N];
struct SegTree{
	int l,r,mid,len;
	int sum,Min,Max;
	bool lazy,__lazy,lazyr;
	SegTree(){}
	SegTree(int __l,int __r){
		l = __l; r = __r; mid = (l+r)>>1; len = r-l+1;
		lazy = __lazy = lazyr = false;
		sum = Min = Max = 0;
	}
}t[N<<2];

void Do(SegTree &res,SegTree res1,SegTree res2){
	res.Min = min(res1.Min , res1.sum + res2.Min);
	res.Max = max(res1.Max , res1.sum + res2.Max);
	res.sum = res1.sum + res2.sum;
}

void Del(int rt,int val){
	if(val == 1){
		t[rt].sum = t[rt].len; t[rt].Min = 1; t[rt].Max = t[rt].len;
		t[rt].lazy = true; t[rt].__lazy = t[rt].lazyr = false;
	}
	else{
		t[rt].sum = -t[rt].len; t[rt].Min = -t[rt].len; t[rt].Max = -1;
		t[rt].__lazy = true; t[rt].lazy = t[rt].lazyr = false;
	}
}

void Reverse(int rt){ 
	int tmp = t[rt].Min , __tmp = t[rt].Max;
	t[rt].sum = -t[rt].sum; t[rt].Min = -__tmp; t[rt].Max = -tmp;
	t[rt].lazyr = true; t[rt].lazy = t[rt].__lazy = false;
}

void PushUp(int rt){
	t[rt].sum = t[lson(rt)].sum + t[rson(rt)].sum;
	t[rt].Min = min(t[lson(rt)].Min , t[lson(rt)].sum + t[rson(rt)].Min);
	t[rt].Max = max(t[lson(rt)].Max , t[lson(rt)].sum + t[rson(rt)].Max);
}

void PushDown(int rt){
	if(t[rt].lazy){
		Del(lson(rt),1); 
		Del(rson(rt),1);
		t[rt].lazy = false;
	}
	else if(t[rt].__lazy){
		Del(lson(rt),-1);
		Del(rson(rt),-1);
		t[rt].__lazy = false;
	}
	else if(t[rt].lazyr){
		if(t[lson(rt)].lazy){
			Del(lson(rt),-1);
		}
		else if(t[lson(rt)].__lazy){
			Del(lson(rt),1);
		}
		else if(t[lson(rt)].lazyr){
			Reverse(lson(rt));
			t[lson(rt)].lazyr = false;
		}
		else{
			Reverse(lson(rt));
		}

		if(t[rson(rt)].lazy){
			Del(rson(rt),-1);
		}
		else if(t[rson(rt)].__lazy){
			Del(rson(rt),1);
		}
		else if(t[rson(rt)].lazyr){
			Reverse(rson(rt));
			t[rson(rt)].lazyr = false;
		}
		else{
			Reverse(rson(rt));
		}

		t[rt].lazyr = false;
	}
}

void build(int rt,int a,int b){
	t[rt] = SegTree(a,b);
	if(a == b){
		if(str[a] == '('){
			t[rt].Min = t[rt].Max = t[rt].sum = 1; t[rt].lazy = true;		
		}
		else{
			t[rt].Min = t[rt].Max = t[rt].sum = -1; t[rt].__lazy = true;
		}
		return;
	}
	int mid = t[rt].mid;
	build(lson(rt),a,mid);
	build(rson(rt),mid+1,b);
	PushUp(rt);
}

void updata_set(int rt,int a,int b,int val){
	if(t[rt].l == a && t[rt].r == b){
		Del(rt,val);
		return ;
	}
	PushDown(rt);
	int mid = t[rt].mid;
	if(b <= mid)
		updata_set(lson(rt),a,b,val);
	else if(a > mid)
		updata_set(rson(rt),a,b,val);
	else{
		updata_set(lson(rt),a,mid,val);
		updata_set(rson(rt),mid+1,b,val);
	}
	PushUp(rt);
}

void updata_reverse(int rt,int a,int b){
	if(t[rt].l == a && t[rt].r == b){
		if(t[rt].lazy){
			Del(rt,-1);
		}
		else if(t[rt].__lazy){
			Del(rt,1);
		}
		else if(t[rt].lazyr){
			Reverse(rt);
			t[rt].lazyr = false;
		}
		else{
			Reverse(rt);
		}
		return ;
	}
	PushDown(rt);
	int mid = t[rt].mid;
	if(b <= mid)
		updata_reverse(lson(rt),a,b);
	else if(a > mid)
		updata_reverse(rson(rt),a,b);
	else{
		updata_reverse(lson(rt),a,mid);
		updata_reverse(rson(rt),mid+1,b);
	}
	PushUp(rt);
}

SegTree query(int rt,int a,int b){
	if(t[rt].l == a && t[rt].r == b){
		return t[rt];
	}
	PushDown(rt);
	int mid = t[rt].mid;
	if(b <= mid)
		return query(lson(rt),a,b);
	else if(a > mid)
		return query(rson(rt),a,b);
	else{
		SegTree res1 = query(lson(rt),a,mid);
		SegTree res2 = query(rson(rt),mid+1,b);
		SegTree res = SegTree(a,b);
		Do(res,res1,res2);
		return res;
	}
}

int main(){
	int T,n,q;
	scanf("%d",&T);
	for(int cas = 1; cas <= T; cas++){
		scanf("%d",&n);
		scanf("%s",str);
		build(1,0,n-1);
		scanf("%d",&q);
		printf("Case %d:\n",cas);
		while(q--){
			char op[10]; int a,b;
			scanf("%s",op);
			if(op[0] == 's'){
				int val; char s[5];
				scanf("%d%d%s",&a,&b,s);
				val = (s[0] == '(' ? 1 : -1);
				updata_set(1,a,b,val);
			}
			else if(op[0] == 'r'){
				scanf("%d%d",&a,&b);
				updata_reverse(1,a,b);
			}
			else{
				scanf("%d%d",&a,&b);
				SegTree res = query(1,a,b);
				if(res.sum != 0 || res.Min < 0)
					puts("NO");
				else puts("YES");
			}
		}
		puts("");
	}
	return 0;
}