LGP11369 [Ynoi 2024-R] 弥留之国的爱丽丝 学习笔记
Luogu Link
前言
又是 bitset 维护 \(\texttt{DAG}\) 可达性，又是操作序列分块的，大典题呐看来这是。
题意简述
给定一个 \(n\) 点 \(m\) 边的有向图。边有黑白两种颜色。一开始所有边都是黑色的。
\(q\) 次操作：
1 k：反转第 \(k\) 条边的颜色。2 u v：询问能否只走黑色的边从 \(u\) 走到 \(v\)。
\(n\le 5\times 10^4,1\le m,q\le 10^5\)。没有自环。
时限 \(\text{8.00s}\)。
做法解析
观察到原问题显然不弱于 \(\texttt{DAG}\) 可达性，而 \(\texttt{DAG}\) 可达性是 \(O(\frac{n^2}{\omega})\) 的。所以我们大概也得想某种类似复杂度的东西。
没有修改是好做的，bitset 维护可达性即可。有修改呢？这种一眼看上去就是 \(\text{polylog}\) 干不了的图论操作问题，直接考虑操作分块。
设我们 \(B\) 个操作分一块。对于这些操作中被询问或有边被修改的点，我们令其为关键点。显然，在这 \(B\) 个操作中，不通过关键点的，非关键点之间的连通性状况是不变的。所以你可以先用一个 \(tarjan\) 加缩点处理一下这些分量的可达性。然后你再维护一下在不考虑带修边时关键点两两间的连通性。
然后你再一个一个操作来维护即可，修改就改几个信息，查询就一个经 bitset 优化的 \(\texttt{bfs}\)，详见代码实现。
最后总的下来时间复杂度是 \(O(\frac{q}{B}\times(\frac{B(n+m)}{w}+\frac{B^2}{w}))\)。自己调一下块长发现 \(B=400\) 时表现较好。
代码实现
分拆讲解
讲解一下程序的主要部分：void solve(int ql,int qr){}。
for(int i=ql;i<=qr;i++){auto add=[&](int u)->void {if(cid[u]==-1)kpos[kcnt]=u,cid[u]=kcnt++;};if(C[i].o==1)add(E[C[i].x].u),add(E[C[i].x].v),che[C[i].x]=true;if(C[i].o==2)add(C[i].x),add(C[i].y);
}
这一段是在加入所有关键点、标记关键边。
for(int i=1;i<=M;i++)if(vld[i]&&!che[i])Gr1[E[i].u].push_back(E[i].v);
for(int i=1;i<=N;i++)if(!dfn[i])tarjan(i);
for(int u=1;u<=N;u++)for(int v : Gr1[u])if(bel[u]!=bel[v])Gr2[bel[u]].push_back(bel[v]);
这一段是对在这段操作序列分块中没有修改的边跑 tarjan 并建立缩点后的新图。
for(int i=0;i<kcnt;i++)F[bel[kpos[i]]][i]=1;
for(int u=1;u<=ccnt;u++)for(int v : Gr2[u])F[u]|=F[v];
for(int x=0;x<kcnt;x++)for(int y=0;y<kcnt;y++)T1[x][y]=F[bel[kpos[x]]][y];
for(int i=1,x,y;i<=M;i++)if(vld[i]&&che[i])x=cid[E[i].u],y=cid[E[i].v],ens[x][y]++,T2[x][y]=1;
这里是在处理连通性：
F[x][y]表示分量 \(x\) 到关键点 \(y\) 的连通性。处理它就是一个复杂度瓶颈：\(O(\frac{B(n+m)}{w})\) 每操作序列分块。T1[x][y]表示关键点 \(x\) 到关键点 \(y\) 的连通性，ens[x][y]表示在当前操作序列块内，有多少条当前为黑的边直接连通了 \(x\) 和 \(y\)，之后 \(\texttt{dfs}\) 就要用到这个转移可达性。T2[x][y]就是ens[x][y]的布尔版本。
for(int i=ql,x,y;i<=qr;i++){auto [co,cx,cy]=C[i];if(co==1){vld[cx]^=1,x=cid[E[cx].u],y=cid[E[cx].v];ens[x][y]+=(vld[cx]?1:-1),T2[x][y]=ens[x][y];}if(co==2){vis.set(),vis[cid[cx]]=0;queue<int> q;q.push(cid[cx]);while(!q.empty()){int u=q.front();q.pop();auto tmp=vis&(T1[u]|T2[u]);for(int v=tmp._Find_first();v<kcnt;v=tmp._Find_next(v))vis[v]=0,q.push(v);}ans[i]=!vis[cid[cy]];}
}
aftinit(ql,qr);
修改操作的代码很易懂。重点讲下查询。
显然这个查询是一个 \(\texttt{bfs}\)，虽然它和一般的 \(\texttt{bfs}\) 有点区别。我们发现这次我们的 vis 数组初值居然是全 \(1\) 而非全 \(0\)。
这是因为我们要利用
bitset优化 \(\texttt{bfs}\)。怎么优化？bitset有找到第一个值为 \(1\) 下标的方法._Find_first()和找到下标 \(x\) 后下一个值为 \(1\) 的下标的方法._Find_next(x)。因为bitset在查找时是每 \(w\) 位一比较，所以它快。因此，我们要让可达为 \(1\)，不可达为 \(0\)。
这玩意实际上就类似于“邻接矩阵”。做就完了。最后记得该清空的东西清空。
完整代码
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=5e4+5,MaxM=1e5+5,Ksiz=4e2+5,KK=Ksiz<<1;
int N,M,Q,X,Y,Z,Opt,B=400,ans[MaxM];
struct edge{int u,v;}E[MaxM];
int vld[MaxM],che[MaxM];
struct quer{int o,x,y;}C[MaxM];
int dfn[MaxN],low[MaxN],ntot,ccnt;
int stk[MaxN],ktp,bel[MaxN];
vector<int> Gr1[MaxN],Gr2[MaxN];
void tarjan(int u){dfn[u]=low[u]=++ntot,stk[++ktp]=u;for(int v : Gr1[u]){if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);else if(!bel[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){ccnt++;for(int x=0;x!=u;ktp--)x=stk[ktp],bel[x]=ccnt;}
}
int cid[MaxN],kcnt,kpos[KK],ens[KK][KK];
bitset<KK> vis,F[MaxN],T1[KK],T2[KK];
void aftinit(int ql,int qr){for(int i=ql;i<=qr;i++)if(C[i].o==1)che[C[i].x]=false;for(int i=1;i<=ccnt;i++)F[i].reset(),Gr2[i].clear();for(int i=0;i<kcnt;i++)T1[i].reset(),fill(ens[i],ens[i]+kcnt,0),T2[i].reset(),cid[kpos[i]]=-1;kcnt=ntot=ccnt=0;for(int i=1;i<=N;i++)Gr1[i].clear(),dfn[i]=low[i]=bel[i]=0;
}
void solve(int ql,int qr){for(int i=ql;i<=qr;i++){auto add=[&](int u)->void {if(cid[u]==-1)kpos[kcnt]=u,cid[u]=kcnt++;};if(C[i].o==1)add(E[C[i].x].u),add(E[C[i].x].v),che[C[i].x]=true;if(C[i].o==2)add(C[i].x),add(C[i].y);}for(int i=1;i<=M;i++)if(vld[i]&&!che[i])Gr1[E[i].u].push_back(E[i].v);for(int i=1;i<=N;i++)if(!dfn[i])tarjan(i);for(int u=1;u<=N;u++)for(int v : Gr1[u])if(bel[u]!=bel[v])Gr2[bel[u]].push_back(bel[v]);for(int i=0;i<kcnt;i++)F[bel[kpos[i]]][i]=1;for(int u=1;u<=ccnt;u++)for(int v : Gr2[u])F[u]|=F[v];for(int x=0;x<kcnt;x++)for(int y=0;y<kcnt;y++)T1[x][y]=F[bel[kpos[x]]][y];for(int i=1,x,y;i<=M;i++)if(vld[i]&&che[i])x=cid[E[i].u],y=cid[E[i].v],ens[x][y]++,T2[x][y]=1;for(int i=ql,x,y;i<=qr;i++){auto [co,cx,cy]=C[i];if(co==1){vld[cx]^=1,x=cid[E[cx].u],y=cid[E[cx].v];ens[x][y]+=(vld[cx]?1:-1),T2[x][y]=ens[x][y];}if(co==2){vis.set(),vis[cid[cx]]=0;queue<int> q;q.push(cid[cx]);while(!q.empty()){int u=q.front();q.pop();auto tmp=vis&(T1[u]|T2[u]);for(int v=tmp._Find_first();v<kcnt;v=tmp._Find_next(v))vis[v]=0,q.push(v);}ans[i]=!vis[cid[cy]];}}aftinit(ql,qr);
}
int main(){readis(N,M,Q);for(int i=1;i<=M;i++)readis(E[i].u,E[i].v);fill(vld+1,vld+M+1,1);for(int i=1;i<=Q;i++){readis(Opt,X);if(Opt==2)readi(Y);C[i]={Opt,X,Y};}fill(cid+1,cid+N+1,-1);for(int i=1;i<=Q;i+=B)solve(i,min(i+B-1,Q));for(int i=1;i<=Q;i++)if(C[i].o==2)puts(ans[i]?"YES":"NO");return 0;
}
后记
这个后记是干嘛的。