Visits: 272

CF576E Painting Edges

题意

• 给定一张 $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]$，颜色有两种可能：

1. 染上去了，则颜色是 $x$ 染色时的颜色。
2. 没染上去，则颜色是上一次染色的颜色。

那么判断变成一个单点判断了，分治到那个叶子的时候进行判断就好了。

总时间复杂度 $\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;
}