题解：CF1989F Simultaneous Coloring

· · 题解

CF1989F Simultaneous Coloring 题解

前言

2024/7/6 update：修改了时间复杂度。

题意

给定一个 n\times m 的网格。你可以把一行染成 R 或者把一列 B，你可以同时染色多行或者多列，并如果有交叉的染色你可以控制它为 R 或 B。定义一次染色的代价为选择的行和列的数量的平方。现在有 q 个要求，每个要求为方格 (x,y) 为 R 或 B，问你将达成前 i(i\le q) 个要求的代价分别为多少。

分析

很像一年前的某音的小游戏。

首先考虑平方代价这个东西，显然每次操作选择的数量越少越好，所以我们考虑如何选择。

再考虑，某个格子的颜色是由该格子最后一次染色来决定的，假如第 (x,y) 为 R，那么一定是先染列 y 再染行 x，这样就有了一种顺序，所以我们就可以把行和列抽象成点，然后连边。

这样就可以构造出一张有向图。假设图为 DAG，那么直接拓扑排序就可以构造出一组解，显然此时答案为 0。但是如果图中出现了环，我们就必须同时选择一个环才能成功染色，更具体的，每次通过 Tarjan 来跑出来每个 SCC，对于每个 SCC 单独操作，然后缩点跑拓扑就是一组解。综上，代价即为图的每个大小 >1 的 SCC 的大小的平方和。

但是此时时间复杂度为 O(q(n+m))，显然无法通过此题。

容易想到用并查集来维护 SCC 的合并，所以我们需要用到一种算法来判断每一条边会合并哪些 SCC。

可以考虑把加边通过每个要求的先后时间来整体二分。

我们对于一个当前区间 [l,r]，把 [l,mid] 的边取出来跑 Tarjan，并且在实际跑的时候，只需要跑 [l,r] 的边的左右端点即可，这样一次 Tarjan 的复杂度即为 O(|V|),V\approx \min\{n,2(r-l+1)\}。

如果当前区间 l<r，那么我们把 [l,mid] 且端点在同一 SCC 的边（即有可能在 mid 时刻连接了两个 SCC）递推到下一层 [l,mid] ，把 [1,r] 且不在同一 SCC 的边递推到下一层 [mid+1,r]。

否则如果 l=r，那就记录一下当前 [l,r] 且端点在同一 SCC 的边的时刻，用于最后跑并查集。

整体二分复杂度 O((n+m+q)\log(q))，并查集复杂度 O(q\alpha(n))。

代码

const int N=4e5+2;
int n,m,q,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],flg[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)
        if(!dfn[ed[i].v])dfs(ed[i].v),low[u]=min(low[u],low[ed[i].v]);
        else if(vis[ed[i].v])low[u]=min(low[u],low[ed[i].v]);
    if(dfn[u]==low[u]){
        num++;int x;
        do{
            x=st.top();st.pop();
            id[x]=num,vis[x]=0;
        }while(x!=u);
    }
    return;
}
void solve(int l,int r,vector<Graph>G){
    int mid=(l+r)>>1;
    en=cnt=num=0;
    for(Graph i:G)
        first[i.u]=first[i.v]=
        dfn[i.u]=dfn[i.v]=0,
        vis[i.u]=vis[i.v]=0;
    for(Graph i:G)
        if(i.tim<=mid)add(i.u,i.v);
    for(Graph i:G){
        if(!dfn[i.u])dfs(i.u);
        if(!dfn[i.v])dfs(i.v);
    }
    if(l==r){
        for(Graph i:G)if(id[i.u]==id[i.v])E[mid].push_back(i.tim);
        return;
    }
    vector<Graph>Gl,Gr;
    for(Graph 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];
inline int find(int v){return fa[v]==v?v:fa[v]=find(fa[v]);}
inline int pf(const int x){return x==1?0:x*x;}
void merge(int x,int y){
    x=find(x);y=find(y);
    if(x!=y){
        ans-=pf(siz[x]),ans-=pf(siz[y]);
        if(siz[x]<siz[y])swap(x,y);
        fa[y]=x,siz[x]+=siz[y];
        ans+=pf(siz[x]);
    }
}
signed main(){
    n=read();m=read();q=read();
    vector<Graph>G;
    for(int i=1;i<=q;i++){
        int x=read(),y=read()+n;
        if(getchar()=='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);
        printf("%lld\n",ans);
    }
    return 0;
}