[Medium-Hard] CF1989F Simultaneous Coloring

简要题意

有一个 $n\times m$ 的网格，初始时每个格子都是白色的。有两种染色方法：将一行所有格子染红、将一列所有格子染蓝。

有 $q$ 次操作，每次操作给出 $(x,y,c)$ 表示单元格 $(x,y)$ 的颜色必须为 $c$。

每次操作结束后，你需要先将网格恢复到初始状态，然后进行若干次染色。注意你可以将 $k$ 个染色策略同时进行，花费 $[k>1]k^2$ 的代价，如果一个单元格受到多个染色方法控制，你可以独立选择其中一种染色方法对其染色。输出满足目前所有限制的最小代价总和。

$1\leq n,m,q\leq 2\times 10^5$。

思路

染色操作受到染色的时刻影响。对于限制 $(x,y,\mathrm{R})$ 即对行 $x$ 的操作必须在 $y$ 之后，$(x,y,\mathrm{B})$ 即对列 $y$ 的操作必须在 $x$ 之后。

可以考虑建图，对于第一种限制，连边 $(C(y),R(x))$，对于第二种限制，连边 $(R(x),C(y))$，则同一个强连通分量的所有点必须同时完成。

由于 $a_1^2+a_2^2+\cdots+a_n^2<(a_1+a_2+\cdots+a_n)^2$，所以答案就是所有大于 $1$ 的强连通分量的大小平方和。于是我们就需要动态加边维护强连通分量。

对于动态加边维护强连通分量的问题，由于每条边在一个时刻后称为某个强连通分量的一部分后，就永远会在强连通分量中，所以可以考虑二分，由于一个一个二分时间复杂度太大，于是可以整体二分。

对于当前二分区间 $[l,r]$，先对 $[l,\mathrm{mid}]$ 跑一遍 tarjan，对于此时在强连通分量的边，就放到左区间，否则放入右区间。注意对于一条边的端点，应该表示缩点后的点，这个可以用并查集维护。最后我们需要维护强连通分量的大小平方和，同样可以用并查集维护。

时间复杂度 $O(q\log q)$。

代码

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

const int N = 4e5 + 5;
int n, m, q, fa[N], siz[N];
long long ans;

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

void merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return;
    if(siz[x] != 1) ans -= 1ll * siz[x] * siz[x];
    if(siz[y] != 1) ans -= 1ll * siz[y] * siz[y];
    siz[x] += siz[y], fa[y] = x;
    ans += 1ll * siz[x] * siz[x];
}


int dfn[N], low[N], stk[N], top, cnt, bel[N];
bool vis[N];
vector<int> g[N];

void tarjan(int u){
    dfn[u] = low[u] = ++dfn[0], stk[++top] = u, vis[u] = true;
    for(auto v : g[u]){
        if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        cnt++;
        while(stk[top] != u){
            bel[stk[top]] = cnt, vis[stk[top--]] = false;
        }
        bel[u] = cnt, vis[u] = false, top--;
    }
}

void solve(int l, int r, const vector<tuple<int,int,int>> &vct){
    if(l == r){
        if(l > q) return;
        for(auto [x, y, z] : vct) merge(x, y);
        cout << ans << '\n';
        return;
    }
    int mid = (l + r) >> 1;
    vector<tuple<int,int,int>> run, lft, rgt;
    for(auto [x, y, z] : vct) (z <= mid ? run : rgt).emplace_back(x, y, z);
    for(auto& [x, y, z] : run) x = find(x), y = find(y), g[x].push_back(y);
    for(auto [x, y, z] : run){
        if(!dfn[x]) tarjan(x);
    }
    for(auto [x, y, z] : run){
        (bel[x] == bel[y] ? lft : rgt).emplace_back(x, y, z);
    }
    top = 0;
    for(auto [x, y, z] : run) dfn[x] = dfn[y] = 0, g[x].clear();
    solve(l, mid, lft), solve(mid + 1, r, rgt);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    vector<tuple<int,int,int>> vct;
    iota(fa + 1, fa + n + m + 1, 1);
    fill(siz + 1, siz + n + m + 1, 1);
    for(int i=1;i<=q;i++){
        int x, y; char ch;
        cin >> x >> y >> ch;
        if(ch == 'R') vct.emplace_back(y + n, x, i);
        else vct.emplace_back(x, y + n, i);
    }
    solve(1, q + 1, vct);
    return 0;
}

// Written by xiezheyuan