Luogu P2486 [SDOI2011]染色

qwq

我这个角色比较特殊.jpg

主要难点在于维护颜色段数。

线段树维护4个变量:段数t,左端点颜色lc,右端点颜色rc,懒标记tag。

当我们修改完,区间需要合并时,如果左儿子rc == 右儿子lc,说明这是同一段,t值相加之后需要-1。

同理,当我们在询问的时候,需要记录链左端的颜色。

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
#include <bits/stdc++.h>

const int N = 2e5 + 233;
int n, m, num, L, R, c[N];
int tag[N << 2], lc[N << 2], rc[N << 2], t[N << 2];
int dep[N], siz[N], son[N], fa[N], tp[N], id[N], g2r[N];
std::vector<int> e[N];

void pushdown(int p) {
if (!tag[p]) return;
tag[p << 1] = tag[p << 1 | 1] = tag[p];
lc[p << 1] = rc[p << 1] = lc[p];
lc[p << 1 | 1] = rc[p << 1 | 1] = lc[p];
t[p << 1] = t[p << 1 | 1] = 1;
tag[p] = 0;
}

void modify(int p, int l, int r, int pl, int pr, int c) {
if (l >= pl && r <= pr) return (void)(lc[p] = rc[p] = c, t[p] = tag[p] = 1);
int mid = (l + r) >> 1;
pushdown(p);
if (pl <= mid) modify(p << 1, l, mid, pl, pr, c);
if (pr > mid) modify(p << 1 | 1, mid + 1, r, pl, pr, c);
lc[p] = lc[p << 1], rc[p] = rc[p << 1 | 1];
t[p] = t[p << 1] + t[p << 1 | 1];
if (rc[p << 1] == lc[p << 1 | 1]) --t[p];
}

int query(int p, int l, int r, int pl, int pr, int PL, int PR) {
if (l == PL) L = lc[p];
if (r == PR) R = rc[p];
if (l >= pl && r <= pr) return t[p];
int mid = (l + r) >> 1, ret = 0;
pushdown(p);
if (pr <= mid) return query(p << 1, l, mid, pl, pr, PL, PR);
if (pl > mid) return query(p << 1 | 1, mid + 1, r, pl, pr, PL, PR);
ret = query(p << 1, l, mid, pl, mid, PL, PR) + query(p << 1 | 1, mid + 1, r, mid + 1, pr, PL, PR);
if (rc[p << 1] == lc[p << 1 | 1]) --ret;
return ret;
}

void dfs1(int x, int f) {
dep[x] = dep[f] + 1, fa[x] = f, siz[x] = 1;
for (auto y : e[x]) {
if (y == f) continue;
dfs1(y, x);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) son[x] = y;
}
}

void dfs2(int x, int tpp) {
tp[x] = tpp, id[x] = ++num, g2r[num] = x;
if (!son[x]) return;
dfs2(son[x], tpp);
for (auto y : e[x])
if (y != fa[x] && y != son[x]) dfs2(y, y);
}

void change(int x, int y, int c) {
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) std::swap(x, y);
modify(1, 1, n, id[tp[x]], id[x], c);
x = fa[tp[x]];
}
if (dep[x] > dep[y]) std::swap(x, y);
modify(1, 1, n, id[x], id[y], c);
}

int ask(int x, int y) {
int ret = 0, l = -1, r = -1;
while (tp[x] != tp[y]) {
if (dep[tp[x]] < dep[tp[y]]) std::swap(x, y), std::swap(l, r);
ret += query(1, 1, n, id[tp[x]], id[x], id[tp[x]], id[x]);
if (R == l) --ret;
l = L;
x = fa[tp[x]];
}
if (dep[x] > dep[y]) std::swap(x, y), std::swap(l, r);
ret += query(1, 1, n, id[x], id[y], id[x], id[y]);
if (L == l) --ret;
if (R == r) --ret;
return ret;
}

signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", c + i);
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
e[x].push_back(y), e[y].push_back(x);
}
dfs1(1, 0), dfs2(1, 1);
for (int i = 1; i <= n; ++i) modify(1, 1, n, id[i], id[i], c[i]);
for (int i = 1; i <= m; ++i) {
char op[20];
int a, b, c;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'C') {
scanf("%d", &c);
change(a, b, c);
} else {
printf("%d\n", ask(a, b));
}
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×