先说一个简单问题：给定一个 \(n\times m\) 的黑白网格图，每次可以将一行或者一列染成同一种色，判断是否能到达？
经典做法：倒过来考虑，每次将颜色全相同或为 * 的一行全染成 *，判断是否可以将这张图染成全 *。经典网格图转二分图，如果 \(s_{i,j}='W'\) 则将 \(i\) 向 \(j'\) 连一条有向边，否则 \(j'\) 向 \(i\) 连。每次相当于将一个没有出度或入度的点对应的边都删掉，判断是否能把所有边删空。容易发现等价于判断是否存在强连通分量，如果是 DAG，则直接按拓扑序取即可，否则随便找一个 SCC，里面点永远动不了。
不过这个题有额外操作方法，保证了每个 SCC 都也能操作成功，那么这个代价怎么算呢？
upd：不是哥们我读错题了，，，当时这里卡住了以为是个很难的问题，现在发现，它的题意指的是，同时染的格子的颜色可以从这次染这行的和这列的里面随便选一个，不过不能凭空制造！因此本题应该换个角度这样理解：咕咕咕
现在有了这个结论，那么我们只需要求出每个时刻的 SCC 状态即可！！！
受到一些可能是 QOJ 上的经典题的启发，我们想到了分治！不过类似连通性这种直接做分治，会遇到一些很大的问题。我比如把 \(time\leq mid\) 的所有边拿出来跑 SCC，那么现在会产生一个缩点之后是 DAG 的有向图，可是我这些 DAG 边究竟应该放哪里呢？我之后做右半边的时候点是用缩完之后还是之前的呢？？？
所以接下来我们就要明确一下这个常见套路。我们对每条边求出的是，它在第几时刻之后"完成使命"了，也就是说，相连的两个点归到了同一个 SCC。这样，我最后求每个时刻的 SCC 时，只要把挂在这个时刻上的所有边拉出来，缩个并查集就好了。因此，我们可以用 solve(l,r,vector<int>g) 来表示一次分治，要去将 \(g\) 里面所有边得到它们对应的时刻。当然，有可能完成不了使命，我们就将其设为 \(q+1\)，不是大问题。当然，每条边的完成时刻一定不早于出现时刻。所以何时加什么边就很明确了：
先得到一个 \(mid\)。将 \(g\) 中所有 \(time\leq mid\) 的边拉出来跑 SCC，得到一堆强连通块，这样可以求出 \(g\) 中每条边应该归到左，还是右，亦或直接扔掉。具体地，对一个 \(\leq mid\) 的边，如果两点已经属于一个 SCC 了，就归到左边，否则归到右边；\(>mid\) 的边，如果两点已经属于了，就没用可以扔了，否则归到右边，接下来继续递归即可。
看起来很对，不过写代码的时候会产生这样一个问题：用缩前还是缩后的点来着？其实很容易想到肯定是用缩后的点的，不过加入的时间要注意一下，应该是先递归处理左半边，然后把这次的 SCC 缩点做好（可以再用个并查集维护），最后处理右半边。不难做到 \(O(n+q\log q)\)。如果实现地不精细多个 log 也无所谓，只要不写 set 常数应该还好。
代码：
#include<bits/stdc++.h>
using namespace std;
int uu[200005],vv[200005],cx[200005],N;
vector<int>g[400005];
int dfn[400005],low[400005],st[400005],vist[400005];
int col[400005],t1=0,t2=0;
void tarjan(int x){
dfn[x]=low[x]=++t1;
st[++t2]=x,vist[x]=1;
for(auto cu:g[x]){
if(!dfn[cu]){
tarjan(cu);
low[x]=min(low[x],low[cu]);
}else if(vist[cu]){
low[x]=min(low[x],dfn[cu]);
}
}
if(dfn[x]!=low[x])return;
int pp;
do{
pp=st[t2--];vist[pp]=0;
col[pp]=x;
}while(pp!=x);
}
int ff[400005];
int findff(int x){
return x==ff[x]?x:ff[x]=findff(ff[x]);
}
void solve(int l,int r,vector<int>gg){
if(l==r){
for(auto d:gg)cx[d]=l;
return;
}
int mid=(l+r)>>1;
vector<int>se;
for(auto d:gg){
int U=findff(uu[d]),V=findff(vv[d]);
dfn[U]=low[U]=col[U]=vist[U]=0;
dfn[V]=low[V]=col[V]=vist[V]=0;
if(d<=mid){
se.emplace_back(U);se.emplace_back(V);
g[U].emplace_back(V);
}
}
sort(se.begin(),se.end());
se.resize(unique(se.begin(),se.end())-se.begin());
t1=t2=0;
for(auto x:se)if(!dfn[x]){
tarjan(x);
}
vector<int>g1,g2;
for(auto d:gg){
int U=ff[uu[d]],V=ff[vv[d]];
if(d<=mid){
if(col[U]==col[V])g1.emplace_back(d);
else g2.emplace_back(d);
}else{
if(col[U]!=col[V]||!col[U]||!col[V])g2.emplace_back(d);
}
}
vector<pair<int,int>>v;
for(auto x:se){
g[x].clear();
v.emplace_back(x,col[x]);
}
solve(l,mid,g1);
for(auto pi:v){
int fx=findff(pi.first),fy=findff(pi.second);
if(fx!=fy)ff[fx]=fy;
}
solve(mid+1,r,g2);
}
int fa[400005],cnt[400005];
int findfather(int x){
return x==fa[x]?x:fa[x]=findfather(fa[x]);
}
vector<int>v2[200005];
long long f(int x){
return x==1?0:1ll*x*x;
}
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);N=n+m;
for(int i=1;i<=q;++i){
int u,v;char op[15];
scanf("%d%d%s",&u,&v,op+1);
int U=u,V=n+v;
if(op[1]=='B')swap(U,V);
uu[i]=U,vv[i]=V;
}
vector<int>vc;
for(int i=1;i<=q;++i)vc.emplace_back(i);
for(int i=1;i<=N;++i)ff[i]=i;
solve(1,q+1,vc);
for(int i=1;i<=N;++i)fa[i]=i,cnt[i]=1;
for(int i=1;i<=q;++i){
if(cx[i]&&cx[i]<=q)v2[cx[i]].emplace_back(i);
}
long long ans=0;
for(int i=1;i<=q;++i){
for(auto d:v2[i]){
int fu=findfather(uu[d]),fv=findfather(vv[d]);
if(fu!=fv){
fa[fu]=fv;
ans=ans-f(cnt[fu])-f(cnt[fv]);
ans=ans+f(cnt[fv]+=cnt[fu]);
}
}
printf("%lld\n",ans);
}
return 0;
}