题意：一个0\1序列，初始为全1，会把某个点从0变1，或从1变为0，求包含x的最长全1序列长度。
开始想到的解法是：求包含x的最长全1序列长度，那么从x向左找到第一个0的位置，从x向右找到第一个0，这中间的即为所求序列。因此，线段树的每个结点需要维护的信息为mi[k],mx[k]，即最左0和最右0的位置。每次查询时求出[1,x+1)区间中最右的0和[x+1,n+1)区间中最左的0的位置，两者之间元素的数目即为所求长度。
后面看到这篇博客中用线段树维护三个区间长度信息来做。
坑：虽然题目没说有多个case，但是需要处理到EOF啊 😄
第一种解法：
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
using namespace std;
typedef pair<int, int> Pair;
const int MAX_N = 50000 + 10;
const int ST_SIZE = 1 << 17;
int n, m;
// leftmost and rightmost destroyed village
int mi[ST_SIZE], mx[ST_SIZE];
void push_up(int k, int lc, int rc) {
mi[k] = min(mi[lc], mi[rc]);
mx[k] = max(mx[lc], mx[rc]);
}
void build(int k, int l, int r) {
if (l == r - 1) {
mi[k] = n + 1;
mx[k] = 0;
} else {
int lc = 2 * k + 1, rc = 2 * k + 2;
int m = (l + r) / 2;
build(lc, l, m);
build(rc, m, r);
push_up(k, lc, rc);
}
}
void destroy(int k, int l, int r, int x) {
if (x < l || r <= x) {
return;
} else if (l == r - 1) {
mi[k] = x;
mx[k] = x;
} else {
int lc = 2 * k + 1, rc = 2 * k + 2;
int m = (l + r) / 2;
destroy(lc, l, m, x);
destroy(rc, m, r, x);
push_up(k, lc, rc);
}
}
void restore(int k, int l, int r, int x) {
if (x < l || r <= x) {
return;
} else if (l == r - 1) {
mi[k] = n + 1;
mx[k] = 0;
} else {
int lc = 2 * k + 1, rc = 2 * k + 2;
int m = (l + r) / 2;
restore(lc, l, m, x);
restore(rc, m, r, x);
push_up(k, lc, rc);
}
}
Pair query(int k, int l, int r, int a, int b) {
if (b <= l || r <= a) {
return Pair(n + 1, 0);
} else if (a <= l && r <= b) {
return Pair(mi[k], mx[k]);
} else {
int lc = 2 * k + 1, rc = 2 * k + 2;
int m = (l + r) / 2;
Pair p1 = query(lc, l, m, a, b);
Pair p2 = query(rc, m, r, a, b);
return Pair(min(p1.first, p2.first), max(p1.second, p2.second));
}
}
int main() {
while (scanf("%d %d", &n, &m) != EOF) {
build(0, 1, n + 1);
stack<int> stk;
for (int i = 0; i < m; i++) {
char event;
int x;
scanf(" %c", &event);
if (event == 'R') {
if (stk.empty()) continue;
x = stk.top(); stk.pop();
restore(0, 1, n + 1, x);
} else {
scanf("%d", &x);
if (event == 'D') {
// destory destroyed village ?
stk.push(x);
destroy(0, 1, n + 1, x);
} else {
Pair p1 = query(0, 1, n + 1, 1, x + 1);
Pair p2 = query(0, 1, n + 1, x, n + 1);
printf("%d\n", max(0, p2.first - (p1.second + 1)));
}
}
}
}
return 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
using namespace std;
const int MAX_N = 50000 + 10;
const int ST_SIZE = 1 << 17;
int N, M;
int ls[ST_SIZE], rs[ST_SIZE], ms[ST_SIZE];
void push_up(int k, int l, int r) {
ls[k] = ls[lc] == m - l ? ls[lc] + ls[rc] : ls[lc];
rs[k] = rs[rc] == r - m ? rs[rc] + rs[lc] : rs[rc];
ms[k] = max(rs[lc] + ls[rc], max(ms[lc], ms[rc]));
}
void build(int k, int l, int r) {
if (l == r - 1) {
ls[k] = rs[k] = ms[k] = 1;
} else {
build(lc, l, m);
build(rc, m, r);
push_up(k, l, r);
}
}
void update(int k, int l, int r, int a, int x) {
if (a < l || r <= a) {
return;
} else if (l == r - 1) {
ls[k] = rs[k] = ms[k] = x;
} else {
update(lc, l, m, a, x);
update(rc, m, r, a, x);
push_up(k, l, r);
}
}
int query(int k, int l, int r, int a) {
if (a < l || r <= a) {
return 0;
} else if (l == r - 1) {
return ms[k];
} else {
int res = max(query(lc, l, m, a), query(rc, m, r, a));
if (m - rs[lc] <= a && a < m + ls[rc]) {
res = max(res, rs[lc] + ls[rc]);
}
return res;
}
}
int main() {
while (scanf("%d %d", &N, &M) != EOF) {
build(0, 1, N + 1);
stack<int> stk;
for (int i = 0; i < M; i++) {
char event;
int x;
scanf(" %c", &event);
if (event == 'R') {
if (stk.empty()) continue;
x = stk.top(); stk.pop();
update(0, 1, N + 1, x, 1);
} else {
scanf("%d", &x);
if (event == 'D') {
// destory destroyed village ?
stk.push(x);
update(0, 1, N + 1, x, 0);
} else {
printf("%d\n", query(0, 1, N + 1, x));
}
}
}
}
return 0;
}