「BZOJ 2243」染色-树链剖分

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作,操作有 $2$ 类:

  1. 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$
  2. 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量

链接

BZOJ 2243

题解

用线段树维护当前区间最左端的颜色和最右端的颜色,以及区间中的颜色段数。

区间合并的时候要注意,左儿子的右端点和右儿子的左端点颜色相同的话,要减去一。

还有一个问题是当前剖到的链与上一次的链在相交的边缘可能颜色相同,如果颜色相同答案需要减一。

代码

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
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 2243」染色 05-09-2017
* 树链剖分
* @author xehoth
*/
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
using IO::io;
const int MAXN = 100000;
const int MAXM = MAXN * 4;
struct Graph {
typedef std::vector<int> Vector;
Vector edge[MAXN + 1];
inline void addEdge(const int u, const int v) {
edge[u].push_back(v), edge[v].push_back(u);
}
inline Vector &operator[](const int i) { return edge[i]; }
};
struct Node {
Node *lc, *rc;
int lColor, rColor;
int tag, sum;
Node();
inline void *operator new(size_t);
inline void cover(int c) { lColor = rColor = c, sum = 1, tag = c; }
inline void pushDown(int l, int r);
inline void maintain();
} pool[MAXM + 1], *cur = pool + 1, *null = pool;
Node::Node() : lc(null), rc(null), lColor(0), rColor(0), sum(1), tag(-1) {}
inline void *Node::operator new(size_t) { return cur++; }
inline void Node::pushDown(int l, int r) {
if (tag == -1 || l == r) return;
lc->cover(tag), rc->cover(tag), tag = -1;
maintain();
}
inline void Node::maintain() {
if (this == null) return;
sum = lc->sum + rc->sum - (rc->lColor == lc->rColor);
lColor = lc->lColor, rColor = rc->rColor;
}
class SegmentTree {
private:
Node *root;
int n;
inline void build(Node *&p, int l, int r, const int *a, const int *id) {
p = new Node();
if (l == r) {
p->lColor = p->rColor = a[id[l]];
return;
}
register int mid = l + r >> 1;
build(p->lc, l, mid, a, id), build(p->rc, mid + 1, r, a, id);
p->maintain();
}
inline int query(Node *p, int l, int r, int s, int t) {
if (s <= l && t >= r) return p->sum;
p->pushDown(l, r);
register int mid = l + r >> 1, ret = 0;
register int tmp =
(p->lc->rColor == p->rc->lColor) && s <= mid && t > mid;
if (s <= mid) ret += query(p->lc, l, mid, s, t);
if (t > mid) ret += query(p->rc, mid + 1, r, s, t);
return ret - tmp;
}
inline void modify(Node *p, int l, int r, int s, int t, int c) {
if (s <= l && t >= r) {
p->cover(c);
return;
}
p->pushDown(l, r);
register int mid = l + r >> 1;
if (s <= mid) modify(p->lc, l, mid, s, t, c);
if (t > mid) modify(p->rc, mid + 1, r, s, t, c);
p->maintain();
}
public:
inline void init() {
null->lc = null->rc = null, null->sum = 0;
null->tag = -1, null->lColor = null->rColor = 0;
}
inline void build(const int l, const int r, const int *a, const int *id) {
this->n = r;
build(root, l, r, a, id);
}
inline int query(int l, int r) { return query(root, 1, n, l, r); }
inline void modify(int l, int r, int c) { modify(root, 1, n, l, r, c); }
inline int getColor(int pos) {
register int l = 1, r = n, mid;
Node *p = root;
for (; l != r;) {
p->pushDown(l, r);
mid = l + r >> 1;
if (pos <= mid)
p = p->lc, r = mid;
else
p = p->rc, l = mid + 1;
}
return p->lColor;
}
};
struct HeavyLightChainDecomposition {
Graph g;
SegmentTree segmentTree;
typedef Graph::Vector::iterator Iterator;
int sz[MAXN + 1], dep[MAXN + 1], fa[MAXN + 1], idx;
int top[MAXN + 1], son[MAXN + 1], pos[MAXN + 1], id[MAXN + 1];
bool vis[MAXN + 1];
inline void dfs1(const int u) {
vis[u] = true, sz[u] = 1, dep[u] = dep[fa[u]] + 1;
for (Iterator v = g[u].begin(); v != g[u].end(); v++) {
if (!vis[*v]) {
fa[*v] = u, dfs1(*v), sz[u] += sz[*v];
sz[*v] > sz[son[u]] ? son[u] = *v : 0;
}
}
}
inline void dfs2(const int u) {
vis[u] = false, pos[u] = ++idx, id[idx] = u,
top[u] = (u == son[fa[u]] ? top[fa[u]] : u);
for (Iterator v = g[u].begin(); v != g[u].end(); v++)
if (*v == son[u]) dfs2(*v);
for (Iterator v = g[u].begin(); v != g[u].end(); v++)
if (vis[*v]) dfs2(*v);
}
inline int lca(int u, int v) {
while (top[u] != top[v])
dep[top[u]] < dep[top[v]] ? v = fa[top[v]] : u = fa[top[u]];
return dep[u] < dep[v] ? u : v;
}
inline void cut(int root = 1) { dfs1(root), dfs2(root); }
int color[MAXN + 1];
inline void modify(int u, int v, int w) {
while (top[u] != top[v]) {
dep[top[u]] < dep[top[v]] ? std::swap(u, v) : (void)0;
segmentTree.modify(pos[top[u]], pos[u], w);
u = fa[top[u]];
}
dep[u] < dep[v] ? std::swap(u, v) : (void)0;
segmentTree.modify(pos[v], pos[u], w);
}
inline int query(int u, int v) {
register int ret = 0;
while (top[u] != top[v]) {
dep[top[u]] < dep[top[v]] ? std::swap(u, v) : (void)0;
ret += segmentTree.query(pos[top[u]], pos[u]);
if (segmentTree.getColor(pos[top[u]]) ==
segmentTree.getColor(pos[fa[top[u]]]))
ret--;
u = fa[top[u]];
}
dep[u] < dep[v] ? std::swap(u, v) : (void)0;
return ret + segmentTree.query(pos[v], pos[u]);
}
inline void solve() {
register int n, m;
io >> n >> m;
for (register int i = 1; i <= n; i++) io >> color[i];
for (register int i = 1, u, v; i < n; i++)
io >> u >> v, g.addEdge(u, v);
cut(), segmentTree.init();
segmentTree.build(1, n, color, id);
static char cmd[5];
for (register int u, v, w, t; m--;) {
io >> cmd;
switch (cmd[0]) {
case 'C':
io >> u >> v >> w;
modify(u, v, w);
break;
case 'Q':
io >> u >> v;
io << query(u, v) << '\n';
break;
default:
assert(false);
}
}
}
} task;
}
int main() {
task.solve();
return 0;
}
分享到