CF576E Painting Edges 题解
Visits: 316
题意
- 给定一张 $n$ 个点 $m$ 条边的无向图。
- 一共有 $k$ 种颜色,一开始,每条边都没有颜色。
- 定义合法状态为仅保留染成 $k$ 种颜色中的任何一种颜色的边,图都是一张二分图。
- 有 $q$ 次操作,第 $i$ 次操作将第 $e_i$ 条边的颜色染成 $c_i$。
- 但并不是每次操作都会被执行,只有当执行后仍然合法,才会执行本次操作。
- 你需要判断每次操作是否会被执行。
- $n,m,q \le 5 \times 10^5$,$k \le 50$。
题解
类似 P5787 二分图 /【模板】线段树分治(学习笔记 & 题解)。
只是一个可撤销并查集变成了 $k$ 个,以及要多加一个判断。
这个判断不太好弄,考虑把判断和区间操作分开进行。
区间操作其实就是,对于一条边的两次染色 $x,y$,染色区间为 $[x+1,y-1]$,颜色有两种可能:
- 染上去了,则颜色是 $x$ 染色时的颜色。
- 没染上去,则颜色是上一次染色的颜色。
那么判断变成一个单点判断了,分治到那个叶子的时候进行判断就好了。
总时间复杂度 $\mathcal O(m \log n \log q)$。
代码
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;
}