「BZOJ-1095」捉迷藏-动态树分治+堆

捉迷藏 $Jiajia$ 和 $Wind$ 是一对恩爱的夫妻,并且他们有很多孩子。某天,$Jiajia$、$Wind$ 和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由 $N$ 个屋子和 $N-1$ 条双向走廊组成,这 $N-1$ 条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,$Jiajia$ 负责找,而 $Wind$ 负责操纵这 $N$ 个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,$Jiajia$ 希望知道可能的最远的两个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: $C(hange)$ $i$ 改变第 $i$ 个房间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 $G(ame)$ 开始一次游戏,查询最远的两个关灯房间的距离。

链接

BZOJ1095

题解

动态树分治,由于树高只有 $O(logn)$,我们可以每个节点记录两个堆,第一个堆记子树中所有节点到父亲节点的距离,第二个堆记录所有子节点的堆顶,那么一个节点的堆 $2$ 中的最大和次大加起来就是子树中经过这个节点的最长链,然后我们最后开一个全局的堆,记录所有堆2中最大值和次大值之和,那么全局的堆顶就是答案。
注意:这样做在 BZOJ 上是能过的,SuperOJ会TLE。

代码

动态树分治+堆

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
#include <bits/stdc++.h>
static const int IO_LEN = 65536 / 2;
inline char read() {
static char buf[IO_LEN], *ioh, *iot;
if (iot == ioh) {
iot = (ioh = buf) + fread(buf, 1, IO_LEN, stdin);
if (iot == ioh) return -1;
}
return *ioh++;
}
inline void read(int &x) {
static char ioc;
for (ioc = read(); !isdigit(ioc); ioc = read());
for (x = 0; isdigit(ioc); ioc = read()) x = (x << 1) + (x << 3) + (ioc ^ '0');
}
char _buf1[IO_LEN + 1], *S1 = _buf1;
inline void fwriteChar(char c) {
if (S1 == _buf1 + IO_LEN) {
fwrite(_buf1, 1, IO_LEN, stdout);
S1 = _buf1;
}
*S1++ = c;
}
inline void flushIO() {
fwrite(_buf1, 1, S1 - _buf1, stdout);
}
inline void fwriteInt(int x) {
if (x > 9) fwriteInt(x / 10);
fwriteChar(x % 10 ^ '0');
}
const int MAXN = 100005;
struct PriorityQueue {
std::priority_queue<int> heap, deleteMark;
inline void insert(const int x) { heap.push(x); }
inline void erase(const int x) { deleteMark.push(x); }
inline void pop() {
while (deleteMark.size() && heap.top() == deleteMark.top()) heap.pop(), deleteMark.pop();
heap.pop();
}
inline int top() {
while (deleteMark.size() && heap.top() == deleteMark.top()) heap.pop(), deleteMark.pop();
return heap.top();
}
inline int secondTop() {
register int tmp = top(); pop();
register int ret = top(); insert(tmp);
return ret;
}
inline int size() {
return heap.size() - deleteMark.size();
}
} s1[MAXN], s2[MAXN], ans;
struct Edge {
int to, next;
bool valid;
} edge[MAXN << 1];
int head[MAXN], tot = 1;
int n, m, cnt;
int father[MAXN];
bool status[MAXN];
int logTwo[MAXN << 1], dpt[MAXN], pos[MAXN], dp[MAXN << 1][20], T;
inline void addEdge(const int x, const int y) {
edge[++tot].to = y;
edge[tot].next = head[x];
head[x] = tot;
}
inline int getSize(const int x, const int from) {
register int i, ret = 1;
for (i = head[x]; i; i = edge[i].next) {
if (edge[i].valid || edge[i].to == from)
continue;
ret += getSize(edge[i].to, x);
}
return ret;
}
inline int getCentreOfGravity(const int x, const int from, const int size, int &cg) {
register int i, ret = 1, flag = true;
for (i = head[x]; i; i = edge[i].next) {
if (edge[i].valid || edge[i].to == from)
continue;
register int tmp = getCentreOfGravity(edge[i].to, x, size, cg);
if (tmp << 1 > size)
flag = false;
ret += tmp;
}
if (size - ret << 1 > size)
flag = false;
if (flag) cg = x;
return ret;
}
inline void dfs(const int x, const int from, const int dpt, PriorityQueue &s) {
s.insert(dpt);
for (register int i = head[x]; i; i = edge[i].next) {
if (edge[i].valid || edge[i].to == from)
continue;
dfs(edge[i].to, x, dpt + 1, s);
}
}
inline void insert(PriorityQueue &s) {
if (s.size() >= 2) {
register int tmp = s.top() + s.secondTop();
ans.insert(tmp);
}
}
inline void erase(PriorityQueue &s) {
if (s.size() >= 2) {
register int tmp = s.top() + s.secondTop();
ans.erase(tmp);
}
}
inline int solve(int x) {
register int i, size = getSize(x, 0), cg;
getCentreOfGravity(x, 0, size, cg);
s2[cg].insert(0);
for (i = head[cg]; i; i = edge[i].next) {
if (!edge[i].valid) {
edge[i].valid = edge[i ^ 1].valid = true;
PriorityQueue s;
dfs(edge[i].to, 0, 1, s);
register int tmp = solve(edge[i].to);
father[tmp] = cg; s1[tmp] = s;
s2[cg].insert(s1[tmp].top());
}
}
insert(s2[cg]);
return cg;
}
inline void dfs(int x, int from) {
dp[pos[x] = ++T][0] = dpt[x] = dpt[from] + 1;
for (register int i = head[x]; i; i = edge[i].next) {
if (edge[i].to != from) {
dfs(edge[i].to, x);
dp[++T][0] = dpt[x];
}
}
}
inline int lcaDis(int x, int y) {
x = pos[x]; y = pos[y];
if (x > y) std::swap(x, y);
int L = logTwo[y - x + 1];
return std::min(dp[x][L], dp[y - (1 << L) + 1][L]);
}
inline int distance(int x, int y) {
return dpt[x] + dpt[y] - 2 * lcaDis(x, y);
}
inline void turnOn(int x) {
register int i;
erase(s2[x]);
s2[x].insert(0);
insert(s2[x]);
for (i = x; father[i]; i = father[i]) {
erase(s2[father[i]]);
if (s1[i].size()) s2[father[i]].erase(s1[i].top());
s1[i].insert(distance(father[i], x));
if (s1[i].size()) s2[father[i]].insert(s1[i].top());
insert(s2[father[i]]);
}
}
inline void turnOff(int x) {
int i;
erase(s2[x]);
s2[x].erase(0);
insert(s2[x]);
for (i = x; father[i]; i = father[i]) {
erase(s2[father[i]]);
if (s1[i].size()) s2[father[i]].erase(s1[i].top());
s1[i].erase(distance(father[i], x));
if (s1[i].size()) s2[father[i]].insert(s1[i].top());
insert(s2[father[i]]);
}
}
int main() {
register int i, j, x, y;
static char p;
read(n); cnt = n;
for (i = 1; i < n; i++) {
read(x), read(y);
addEdge(x, y); addEdge(y, x);
}
solve(1);
dfs(1, 0);
for (i = 2; i <= T; i++)
logTwo[i] = logTwo[i >> 1] + 1;
for (j = 1; j <= logTwo[T]; j++)
for (i = 1; i + (1 << j) - 1 <= T; i++)
dp[i][j] = std::min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
for (i = 1; i <= n; i++)
status[i] = true;
read(m);
for (i = 1; i <= m; i++) {
p = read();
while (!isalpha(p)) p = read();
if (p == 'G') {
if (cnt <= 1)
fwriteInt(cnt - 1), fwriteChar('\n');
else
fwriteInt(ans.top()), fwriteChar('\n');
} else {
read(x);
if (status[x] == true) {
--cnt; status[x] = false;
turnOff(x);
} else {
++cnt; status[x] = true;
turnOn(x);
}
}
}
flushIO();
return 0;
}

括号序列+线段树

来自function2

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
#include <cstdio>
#include <iostream>
#define maxn 100000
const int inf = 1 << 25;
using namespace std;
int vis[maxn + 10];
struct node {
int l1, l2, r1, r2, c1, c2, dis;
void val(int x) {
c1 = c2 = 0;
l1 = l2 = r1 = r2 = dis = -inf;
if (x == -1)c2 = 1;
else if (x == -2)c1 = 1;
else if (vis[x] == 1)l1 = l2 = r1 = r2 = 0;
}
void merge(node &a, node &b) {
c1 = a.c1 + max(0, b.c1 - a.c2);
c2 = b.c2 + max(0, a.c2 - b.c1);
dis = max(max(a.dis, b.dis), max(a.r1 + b.l2, a.r2 + b.l1));
l1 = max(a.l1, max(b.l1 - a.c2 + a.c1, b.l2 + a.c2 + a.c1));
l2 = max(a.l2, b.l2 + a.c2 - a.c1);
r1 = max(b.r1, max(a.r1 - b.c1 + b.c2, a.r2 + b.c1 + b.c2));
r2 = max(b.r2, a.r2 + b.c1 - b.c2);
}
} s[maxn * 3 << 2];
int num[maxn * 3 + 10], tot;
void update(int o, int l, int r, int p) {
if (l == r)s[o].val(num[p]);
else {
int m = l + r >> 1;
if (p <= m)update(o << 1, l, m, p);
else update(o << 1 | 1, m + 1, r, p);
s[o].merge(s[o << 1], s[o << 1 | 1]);
}
}
void build(int o, int l, int r) {
if (l == r)s[o].val(num[l]);
else {
int m = l + r >> 1;
build(o << 1, l, m);
build(o << 1 | 1, m + 1, r);
s[o].merge(s[o << 1], s[o << 1 | 1]);
}
}
struct EDGE {
int u, v, next;
} edge[2 * maxn + 10];
int head[maxn + 10], pp;
void adde(int u, int v) {
edge[++pp] = (EDGE) {u, v, head[u]};
head[u] = pp;
}
int pos[maxn + 10];
void dfs(int u, int fa) {
num[++tot] = -1;
pos[num[++tot] = u] = tot;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (v != fa)dfs(v, u);
}
num[++tot] = -2;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)vis[i] = 1;
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
adde(u, v);
adde(v, u);
}
dfs(1, 0);
build(1, 1, tot);
int q, cnt = n;
scanf("%d", &q);
char e[2];
while (q--) {
scanf("%s", e);
if (e[0] == 'G') {
if (cnt == 0)puts("-1");
else if (cnt == 1)puts("0");
else printf("%d\n", s[1].dis);
} else {
int u;
scanf("%d", &u);
cnt += vis[u] = -vis[u];
update(1, 1, tot, pos[u]);
}
}
return 0;
}

分享到