P11369 弥留之国的爱丽丝
题面
题解
我常常追忆过去。
注意到这个题不弱于 DAG 可达性问题，考虑除以 \(w\) 的做法。
对询问分块，我们只考虑块内关键点之间的可达性问题。
假设每 \(B\) 个操作一块，我们将这里被修改的边的端点以及询问涉及的两个点视作关键点，共产生 \(2B\) 个关键点。
然后，对于不在区间内被修改的边，我们直接花 \(O((n+m)\frac{w+B}{w})\) 的时间处理关键点可达性。对于会被修改的边，单独维护它们的状态。询问时考虑 \(\mathrm{bitset}\) 优化搜索即可。
视 \(n,m,q\) 同阶，则时间复杂度大概是 \(O(\frac{n^2}w+\frac{n^2}B+\frac{nB^2}w)\)，取 \(B=\Theta(\sqrt n)\) 或者 \(\Theta(w)\) 均可。
我感觉取 \(B=32\) 会比较好，但没试过。
Code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char c=getchar();
while(c<'0'||c>'9'){
// if(c=='-') f=-f;
c=getchar();
}
while(c>='0'&&c<='9'){
ans=(ans<<3)+(ans<<1)+c-48;
c=getchar();
}
return ans;
}
int n,m,q;
int u[100005],v[100005],col[100005],ky[100005];//col=1为黑，=0为白，是否为关键边
const int B=203;
bitset<B*2+5>g[B*2+5],f[B*2+5];
int key[B*2+5];//关键点->原点
int ku[B+5],kv[B+5],kc[B+5],kid[B+5],num;//关键边
int id[50005];//原点->关键点
int x[100005],y[100005];//操作
int cnt;//关键点数量
vector<int>h1[100005],h2[100005],h3[100005];//原图，反图，缩点后新图的反图
int dfn[100005],now;
bool vis[100005];
int scc[100005],tot;//所在强连通分量编号
bitset<B*2+5>g2[100005];
int in[100005];
void topsort(){
queue<int>q;
for(int i=1;i<=tot;i++){
for(int j=0;j<h3[i].size();j++){
in[h3[i][j]]++;
}
}
for(int i=1;i<=tot;i++){
if(!in[i]) q.push(i);
}
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=0;i<h3[u].size();i++){
in[h3[u][i]]--;
g2[h3[u][i]]|=g2[u];
if(!in[h3[u][i]]) q.push(h3[u][i]);
}
}
}
void dfs1(int u){
vis[u]=1;
for(int i=0;i<h1[u].size();i++){
if(!vis[h1[u][i]]) dfs1(h1[u][i]);
}
dfn[++now]=u;
}
void dfs2(int u,int k){
scc[u]=k;
for(int i=0;i<h2[u].size();i++){
if(!scc[h2[u][i]]) dfs2(h2[u][i],k);
}
}
void rev(int k){
int d=0;
for(int i=1;i<=num;i++){
if(kid[i]==k){
kc[i]^=1;
d=i;
}
}
g[ku[d]][kv[d]]=f[ku[d]][kv[d]];
// cout<<d<<' '<<ku[d]<<' '<<kv[d]<<'\n';
// cout<<g[ku[d]][kv[d]]<<'\n';
for(int i=1;i<=num;i++){
if(ku[i]==ku[d]&&kv[i]==kv[d]&&kc[i]) g[ku[i]][kv[i]]=1;
}
}
bitset<B*2+5>viss;
int qry(int x,int y){
viss.set();
queue<int>q;
q.push(x);
viss[x]=0;
while(!q.empty()){
int u=q.front(); q.pop();
if(u==y) return 1;
bitset<B*2+5>tp=viss&g[u];
viss&=~g[u];
for(int i=tp._Find_first();i<=cnt;i=tp._Find_next(i)){
q.push(i);
}
}
return 0;
}
void solve(int l,int r){
// cout<<"("<<l<<' '<<r<<")\n";
// cout<<"进行预处理：\n";
cnt=0;
for(int i=l;i<=r;i++){
if(y[i]==0){
id[u[x[i]]]=1; id[v[x[i]]]=1;
ky[x[i]]=1;
}else{
id[x[i]]=1; id[y[i]]=1;
}
}
for(int i=1;i<=n;i++){
if(id[i]){
id[i]=++cnt;
key[cnt]=i;
}
}
// cout<<"本轮关键点：";
// for(int i=1;i<=cnt;i++){
// cout<<key[i]<<' ';
// }
// cout<<'\n';
for(int i=1;i<=m;i++){
if(!ky[i]&&col[i]){
h1[u[i]].push_back(v[i]);
h2[v[i]].push_back(u[i]);
}
}
for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
// cout<<"h1: \n";
// for(int i=1;i<=n;i++){
// for(int j=0;j<h1[i].size();j++){
// cout<<i<<"->"<<h1[i][j]<<'\n';
// }
// }
// cout<<"h2: \n";
// for(int i=1;i<=n;i++){
// for(int j=0;j<h2[i].size();j++){
// cout<<i<<"->"<<h2[i][j]<<'\n';
// }
// }
// cout<<"得到dfn序：";
// for(int i=1;i<=n;i++) cout<<dfn[i]<<' ';
// cout<<'\n';
// memset(vis,0,sizeof(vis));
for(int i=n;i>=1;i--) if(!scc[dfn[i]]) dfs2(dfn[i],++tot);
// cout<<"所有节点scc划分结果：\n";
// for(int i=1;i<=n;i++) cout<<scc[i]<<' '; cout<<'\n';
for(int i=1;i<=cnt;i++) g2[scc[key[i]]][i]=1;
for(int i=1;i<=m;i++){
if(!ky[i]&&col[i]&&scc[u[i]]!=scc[v[i]]){
h3[scc[v[i]]].push_back(scc[u[i]]);
}
}
topsort();
// cout<<"所有点到关键点可达性：\n";
// for(int i=1;i<=n;i++){
// for(int j=1;j<=cnt;j++){
// cout<<g2[i][j];
// }
// cout<<'\n';
// }
for(int i=1;i<=cnt;i++) g[i]=f[i]=g2[scc[key[i]]];
// cout<<"关键点到关键点可达性：\n";
// for(int i=1;i<=cnt;i++){
// for(int j=1;j<=cnt;j++){
// cout<<f[i][j];
// }
// cout<<'\n';
// }
for(int i=1;i<=m;i++){
if(ky[i]&&col[i]) g[id[u[i]]][id[v[i]]]=1;
}
for(int i=1;i<=m;i++) if(ky[i]){
num++;
ku[num]=id[u[i]];
kv[num]=id[v[i]];
kc[num]=col[i];
kid[num]=i;
}
//预处理结束，处理询问
for(int i=l;i<=r;i++){
if(!y[i]) rev(x[i]);
else{
// cout<<"现在关键点到关键点可达性：\n";
// for(int i=1;i<=cnt;i++){
// for(int j=1;j<=cnt;j++){
// cout<<g[i][j];
// }
// cout<<'\n';
// }
// cout<<"处理询问："<<id[x[i]]<<' '<<id[y[i]]<<'\n';
int u=qry(id[x[i]],id[y[i]]);
if(u){
putchar('Y'); putchar('E'); putchar('S'); putchar(10);
}
else{
putchar('N'); putchar('O'); putchar(10);
}
}
}
//询问结束，进行更新、清零
for(int i=l;i<=r;i++) if(!y[i]) col[x[i]]^=1;
memset(ky,0,sizeof(ky));
memset(key,0,sizeof(key));
memset(id,0,sizeof(id));
memset(dfn,0,sizeof(dfn));
memset(vis,0,sizeof(vis));
memset(scc,0,sizeof(scc));
memset(in,0,sizeof(in));
memset(ku,0,sizeof(ku));
memset(kv,0,sizeof(kv));
memset(kc,0,sizeof(kc));
memset(kid,0,sizeof(kid));
num=0;
for(int i=1;i<=n;i++){
h1[i].clear(); h2[i].clear(); h3[i].clear();
}
cnt=now=tot=0;
for(int i=1;i<=n;i++) g2[i]=bitset<B*2+5>();
}
int main(){
// ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// cin>>n>>m>>q;
n=read(); m=read(); q=read();
for(int i=1;i<=m;i++){
u[i]=read(); v[i]=read(); col[i]=1;
}
for(int i=1;i<=q;i++){
y[i]=read(); x[i]=read();
if(y[i]==2) y[i]=read();
else y[i]=0;
}
// for(int i=1;i<=q;i++) cout<<x[i]<<'_'<<y[i]<<'\n';
int beg=1;
for(int i=1;i<=q;i++){
if(i%B==0||i==q){
solve(beg,i);
beg=i+1;
}
}
return 0;
}