BZOJ2243: [SDOI2011]染色

命題

給定一棵有n個節點的無根樹和m個操作,操作有2類:
1. 將節點a到節點b路徑上所有點都染成顏色c。
2. 詢問節點a到節點b路徑上的顏色段數量(連續相同顏色被認為是同一段)。


類比序列上的顏色段問題,直接套用樹鏈剖分解決即可,需要注意鏈與鏈之間還要進行判斷,實現技巧可以參考下面的代碼第130行的query函數。

#include <cstring> #include <cstdio> #include <algorithm> #include <vector> #include <cassert> using namespace std; const int N = 1e5 + 5; struct Query { int op, a, b, c; Query() {} Query(int op, int a, int b) : op(op), a(a), b(b) {} Query(int op, int a, int b, int c) : op(op), a(a), b(b), c(c) {} } Q[N]; int n, q, _N, hd[N], nxt[2 * N], to[2 * N], w[2 * N], tot, mark; int s[N], dep[N], f[N], df[N], u_son[N], fa[N], top[N]; int tr[8 * N], lc[8 * N], rc[8 * N], tag[8 * N]; int A[N], B[N], F[N]; void up(int p) { tr[p] = tr[p << 1] + tr[p << 1 | 1]; if (rc[p << 1] == lc[p << 1 | 1]) tr[p]--; lc[p] = lc[p << 1]; rc[p] = rc[p << 1 | 1]; } void down(int p) { if (tag[p]) { tag[p << 1] = tag[p << 1 | 1] = tag[p]; lc[p << 1] = rc[p << 1] = tag[p]; lc[p << 1 | 1] = rc[p << 1 | 1] = tag[p << 1 | 1]; tr[p << 1] = tr[p << 1 | 1] = 1; tag[p] = 0; } } void build(int l, int r, int p) { if (l == r) { tr[p] = 1; lc[p] = rc[p] = A[df[l]]; return; } int mid = (l + r) / 2; build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1); up(p); } void update(int l, int r, int L, int R, int x, int p) { if (L <= l && r <= R) { tag[p] = x; lc[p] = rc[p] = x; tr[p] = 1; return; } down(p); int mid = (l + r) / 2; if (L <= mid) update(l, mid, L, R, x, p << 1); if (R > mid) update(mid + 1, r, L, R, x, p << 1 | 1); up(p); } int lst; int query(int l, int r, int L, int R, int p) { if (l > R || r < L) return 0; if (L <= l && r <= R) { assert(lc[p] != 0); int ret = tr[p] - (lst == lc[p]); lst = rc[p]; return ret; } down(p); int mid = (l + r) / 2; return query(l, mid, L, R, p << 1) + query(mid + 1, r, L, R, p << 1 | 1); } int get(int l, int r, int id, int p) { if (l == r) return lc[p]; int mid = (l + r) / 2; down(p); if (id <= mid) return get(l, mid, id, p << 1); else return get(mid + 1, r, id, p << 1 | 1); } void add(int a, int b) { nxt[++tot] = hd[a], to[hd[a] = tot] = b; nxt[++tot] = hd[b], to[hd[b] = tot] = a; } void dfs1(int u, int _fa, int _dep) { fa[u] = _fa; dep[u] = _dep; s[u] = 1; for (int e = hd[u]; e; e = nxt[e]) { int v = to[e]; if (v != _fa) { dfs1(v, u, _dep + 1); s[u] += s[v]; if (!u_son[u] || s[v] > s[u_son[u]]) u_son[u] = v; } } } void dfs2(int u, int id) { top[u] = id; f[u] = ++mark; df[mark] = u; if (!u_son[u]) return; dfs2(u_son[u], id); for (int e = hd[u]; e; e = nxt[e]) { int v = to[e]; if (v != u_son[u] && v != fa[u]) dfs2(v, v); } } void update(int a, int b, int c) { for (; top[a] != top[b]; b = fa[top[b]]) { if (dep[top[b]] < dep[top[a]]) swap(a, b); update(1, mark, f[top[b]], f[b], c, 1); } if (dep[b] < dep[a]) swap(a, b); update(1, mark, f[a], f[b], c, 1); } int Lst[2], cur, ans; void query(int a, int b) { cur = Lst[0] = Lst[1] = ans = 0; for (; top[a] != top[b]; b = fa[top[b]]) { if (dep[top[b]] < dep[top[a]]) swap(a, b), cur ^= 1; lst = 0, ans += query(1, mark, f[top[b]], f[b], 1); if (get(1, mark, f[b], 1) == Lst[cur ^ 1]) ans--; Lst[cur ^ 1] = get(1, mark, f[top[b]], 1); } if (dep[b] <= dep[a]) swap(a, b), cur ^= 1; int tmp; lst = 0, ans += (tmp = query(1, mark, f[a], f[b], 1)); int V = get(1, mark, f[a], 1); int W = get(1, mark, f[b], 1); int Y = Lst[cur ^ 1]; int Z = Lst[cur]; if (Z == V) ans--; if (Y == W) ans--; printf("%d\n", ans); } void discretization() { sort(B + 1, B + _N + 1); _N = unique(B + 1, B + _N + 1) - B; for (int i = 1; i <= n; i++) { int _F = lower_bound(B + 1, B + _N + 1, A[i]) - B; F[_F] = A[i]; A[i] = _F; } for (int i = 1; i <= q; i++) { if (Q[i].op == 0) { int _F = lower_bound(B + 1, B + _N + 1, Q[i].c) - B; F[_F] = Q[i].c; Q[i].c = _F; } } } int main() { scanf("%d%d", &n, &q); _N = n; for (int i = 1; i <= n; i++) scanf("%d", &A[i]), B[i] = A[i]; for (int i = 1; i < n; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); } dfs1(1, 0, 1); dfs2(1, 1); for (int i = 1; i <= q; i++) { char op[5]; int a, b, c; scanf("%s", op); if (op[0] == 'C') scanf("%d%d%d", &a, &b, &c), Q[i] = Query(0, a, b, c), B[++_N] = c; if (op[0] == 'Q') scanf("%d%d", &a, &b), Q[i] = Query(1, a, b); } discretization(); build(1, mark, 1); for (int i = 1; i <= q; i++) { Query &X = Q[i]; if (X.op == 0) update(X.a, X.b, X.c); if (X.op == 1) query(X.a, X.b); } return 0; }
Code language: PHP (php)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注