CF1989F Simultaneous Coloring 题解

题意简述

给定一个 $n \times m$ 的网格，初始无色。有两种操作：

• 将一整行涂成红色（R）；
• 将一整列涂成蓝色（B）。

你可以同时执行多个操作。若同时执行 $k$ 个操作，代价为 $k^2$（$k > 1$）；单独执行一个操作代价为 $0$。同时操作时，行列交叉处的格子颜色可以独立指定。

现有 $q$ 个限制，每个限制形如 $(x_i, y_i, c_i)$，要求该格子最终颜色为 $c_i$（R 或 B）。限制逐个加入，每次加入后输出满足所有限制的最小代价。

$1 \le n, m, q \le 2 \cdot 10^5$。

核心思路

1. 转化为有向图

某个格子的颜色由最后一次操作决定。例如 $(x, y)$ 要求为 R，说明列 $y$ 在行 $x$ 之前被染色（先染列 B，再染行 R，则最终为 R；反之则最终为 B）。因此每条限制对应一条有向边：

• 若要求 R：从列 $y$ 连边到行 $x$（列先，行后）；
• 若要求 B：从行 $x$ 连边到列 $y$（行先，列后）。

图中共 $n+m$ 个点，行点编号 $1 \sim n$，列点编号 $n+1 \sim n+m$。

2. 代价与 SCC

若图是 DAG，可按拓扑序操作，每次单独操作即可满足所有顺序，代价为 $0$。

若图中有环，则环上的点必须同时被操作（否则无法满足先后约束）。每个大小 $>1$ 的 SCC（强连通分量）必须整体同时操作，贡献代价为 $|SCC|^2$。不同 SCC 之间缩点后仍是 DAG，按拓扑序执行即可。

因此总代价 = 所有大小 $>1$ 的 SCC 的大小平方和。

3. 动态加边与整体二分

限制是逐个加入的，我们需对每个前缀计算代价。等价于动态加边，维护 SCC 合并及平方贡献。

对于每条边，我们需要知道它在何时会使两个端点进入同一 SCC。直接对整个序列整体二分：

• 定义时间轴 $[1, q]$。
• 递归处理区间 $[l, r]$，带上当前可能有效的边集 $G$（每条边 $(u,v,t)$ 表示在时刻 $t$ 加入）。
• 取 $mid = (l+r)/2$，将 $\le mid$ 的边建图跑 Tarjan，找出当前形成的 SCC。
• 分治：
  • 对于已在同一 SCC 且 $t \le mid$ 的边，它们可能在 $mid$ 时刻前就已合并，递归到左区间 $[l, mid]$；
  • 对于不在同一 SCC 的边，缩点后（以 SCC 编号为新端点）递归到右区间 $[mid+1, r]$。
• 当 $l = r$ 时，若某边两端点在同一 SCC，则它在时刻 $l$ 触发了合并，记录到 E[l] 中。

这样，我们得到了每条边首次将两个 SCC 合并的时刻。整体二分复杂度 $O((n+m+q) \log q)$，因为每次只建 $O(|V|)$ 的图，$|V|$ 为当前区间涉及的点数。

4. 并查集维护答案

得到每条边的合并时刻后，按时间顺序用并查集合并 SCC：

• 初始每个点独立，代价为 $0$。
• 对于时刻 $i$，处理 E[i] 中的所有边：合并对应的两个 SCC。
• 合并时，若两 SCC 不同，更新总代价：
  • 减去原有 SCC 的大小平方贡献；
  • 合并后加上新 SCC 的大小平方贡献。
• 每次合并后输出当前总代价。

并查集 $O(q \alpha(n+m))$。

复杂度

• 整体二分：$O((n+m+q) \log q)$
• 并查集：$O(q \alpha(n+m))$
• 总复杂度 $\approx O((n+m+q) \log q)$，可通过 $2 \cdot 10^5$ 的数据。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 2;
int n, m, q;
long long ans;

struct Graph {
    int u, v, tim;
};

vector<int> E[N];

struct Edge {
    int nxt, v;
} ed[N];
int en, first[N];
void add(int u, int v) {
    ed[++en] = {first[u], v};
    first[u] = en;
}

int dfn[N], low[N], cnt;
int num, id[N];
bool vis[N];
stack<int> st;

void dfs(int u) {
    dfn[u] = low[u] = ++cnt;
    st.push(u); vis[u] = 1;
    for (int i = first[u]; i; i = ed[i].nxt) {
        int v = ed[i].v;
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], low[v]);
        }
    }
    if (dfn[u] == low[u]) {
        num++;
        int x;
        do {
            x = st.top(); st.pop();
            id[x] = num; vis[x] = 0;
        } while (x != u);
    }
}

void solve(int l, int r, vector<Graph> G) {
    int mid = (l + r) >> 1;
    en = cnt = num = 0;
    for (auto &i : G) {
        first[i.u] = first[i.v] = 0;
        dfn[i.u] = dfn[i.v] = 0;
        vis[i.u] = vis[i.v] = 0;
    }
    for (auto &i : G)
        if (i.tim <= mid) add(i.u, i.v);
    for (auto &i : G) {
        if (!dfn[i.u]) dfs(i.u);
        if (!dfn[i.v]) dfs(i.v);
    }
    if (l == r) {
        for (auto &i : G)
            if (id[i.u] == id[i.v])
                E[mid].push_back(i.tim);
        return;
    }
    vector<Graph> Gl, Gr;
    for (auto &i : G) {
        if (id[i.u] == id[i.v]) {
            if (i.tim <= mid) Gl.push_back(i);
        } else {
            Gr.push_back({id[i.u], id[i.v], i.tim});
        }
    }
    solve(l, mid, Gl);
    solve(mid + 1, r, Gr);
}

int fa[N], siz[N];

int find(int v) { return fa[v] == v ? v : fa[v] = find(fa[v]); }

inline long long pf(int x) { return x == 1 ? 0 : 1LL * x * x; }

void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) {
        ans -= pf(siz[x]) + pf(siz[y]);
        if (siz[x] < siz[y]) swap(x, y);
        fa[y] = x; siz[x] += siz[y];
        ans += pf(siz[x]);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> q;
    vector<Graph> G;
    for (int i = 1; i <= q; i++) {
        int x, y; char c;
        cin >> x >> y >> c;
        y += n;
        if (c == 'R') G.push_back({y, x, i});
        else G.push_back({x, y, i});
    }
    solve(1, q, G);
    for (int i = 1; i <= n + m; i++) fa[i] = i, siz[i] = 1;
    for (int i = 1; i <= q; i++) {
        for (int j : E[i])
            merge(G[j - 1].u, G[j - 1].v);
        cout << ans << '\n';
    }
    return 0;
}