题解 CF576E 【Painting Edges】

xht

2019-12-11 01:29:52

Solution

> [CF576E Painting Edges](https://codeforc.es/contest/576/problem/E) ## 题意 - 给定一张 $n$ 个点 $m$ 条边的无向图。 - 一共有 $k$ 种颜色,一开始,每条边都没有颜色。 - 定义**合法状态**为仅保留**染成 $k$ 种颜色中的任何一种颜色**的边,图都是一张二分图。 - 有 $q$ 次操作,第 $i$ 次操作将第 $e_i$ 条边的颜色染成 $c_i$。 - 但并不是每次操作都会被**执行**,只有当执行后仍然合法,才会执行本次操作。 - 你需要判断每次操作是否会被执行。 - $n,m,q \le 5 \times 10^5$,$k \le 50$。 ## 题解 类似 [P5787 二分图 /【模板】线段树分治](https://www.luogu.com.cn/problem/P5787)([学习笔记 & 题解](https://www.xht37.com/线段树分治-学习笔记/))。 只是一个可撤销并查集变成了 $k$ 个,以及要多加一个判断。 这个判断不太好弄,考虑把判断和区间操作分开进行。 区间操作其实就是,对于一条边的两次染色 $x,y$,染色区间为 $[x+1,y-1]$,颜色有两种可能: 1. 染上去了,则颜色是 $x$ 染色时的颜色。 2. 没染上去,则颜色是上一次染色的颜色。 那么判断变成一个单点判断了,分治到那个叶子的时候进行判断就好了。 总时间复杂度 $\mathcal O(m \log n \log q)$。 ## 代码 ```cpp const int N = 5e5 + 7, K = 51; int n, m, k, q, f[K][N<<1], d[K][N<<1], u[N], v[N], a[N], c[N], p[N]; struct T { int l, r; vi e; } t[N<<2]; struct S { int c, x, z; inline S() {} inline S(int c, int x, int z) : c(c), x(x), z(z) {} }; stack< S > s; void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if (l == r) return; build(ls, l, md), build(rs, md + 1, r); } void ins(int p, int l, int r, int x) { if (t[p].l >= l && t[p].r <= r) return t[p].e.pb(x), void(); if (l <= md) ins(ls, l, r, x); if (r > md) ins(rs, l, r, x); } inline int get(int o, int x) { while (x ^ f[o][x]) x = f[o][x]; return x; } inline void merge(int o, int x, int y) { if (x == y) return; if (d[o][x] > d[o][y]) swap(x, y); int z = d[o][x] == d[o][y]; s.push(S(o, x, z)), f[o][x] = y, d[o][y] += z; } void dfs(int p, int l, int r) { ui o = s.size(); for (ui i = 0; i < t[p].e.size(); i++) { int x = t[p].e[i], a = ::a[x], c = ::c[x], u = ::u[a], v = ::v[a]; if (c) merge(c, get(c, u + n), get(c, v)), merge(c, get(c, v + n), get(c, u)); } if (l == r) { int a = ::a[l], c = ::c[l], u = ::u[a], v = ::v[a]; if (get(c, u) == get(c, v)) prints("NO"), ::c[l] = ::p[a]; else prints("YES"), ::p[a] = ::c[l]; } else dfs(ls, l, md), dfs(rs, md + 1, r); while (s.size() > o) { int c = s.top().c, x = s.top().x, z = s.top().z; s.pop(), d[c][f[c][x]] -= z, f[c][x] = x; } } int main() { rd(n), rd(m), rd(k), rd(q); build(1, 1, q); for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) f[j][i] = i, f[j][i+n] = i + n; for (int i = 1; i <= m; i++) rd(u[i]), rd(v[i]), p[i] = q + 1; for (int i = 1; i <= q; i++) rd(a[i]), rd(c[i]); for (int i = q; i; i--) { int a = ::a[i]; if (i < p[a] - 1) ins(1, i + 1, p[a] - 1, i); p[a] = i; } for (int i = 1; i <= m; i++) p[i] = 0; dfs(1, 1, q); return 0; } ```