P11369 [Ynoi2024] 弥留之国的爱丽丝题解

KobeBeanBryantCox · 2025-08-03 16:16:29 · 题解

P11369 [Ynoi2024] 弥留之国的爱丽丝题解

题目传送门。

好多细节。~~建议别写代码。口胡会了就行。~~

我缩点写的 kosaraju 而不是 tarjan。

题意

给定有向图，初始所有边为黑色。

多次执行两个操作：

把第 i 条边反色；
查询 u 能否只走黑边到达 v。

思路

如果没有一操作，显然缩点后跑 bitset 优化 DAG 可达性。

故原问题不弱于 DAG 可达性问题，因此复杂度不小于 O(\frac{nm}\omega)。

考虑暴力做两个操作。每次查询做 bfs，修改直接改。

考虑优化。考虑对操作分块，每 B 个操作放在一起处理。

考虑处理 [l,r] 的操作。

将当前块内操作一的边都删去（无论黑白），剩下的边在操作的时候不会受到影响。

定义「关键点」为块内操作二的点，以及操作一的边的两个端点，显然「关键点」的个数是 O(B) 的。

对剩下的图做缩点（白色边不能缩），对形成的 DAG 做可达性问题。时间复杂度 O(\frac{nB}\omega)。

::::warning[细节问题] 这里有细节。要用缩点后的图做可达性问题，而不是只用关键点，但是显然时空复杂度不合适，且是错误的。

如果你不信邪你可能会被以下数据卡死：

考虑第一维记录缩点后的点，第二维记录关键点，做可达性问题后再转化成两维都是关键点。 ::::

此时可以维护关键点之间的可达性。记 f_{i,j}=0/1 表示第 i 个关键点到第 j 个可不可达（邻接矩阵）。

此时块内操作等价于：

加删边，这些边一定是在关键点间的。
查询连通性。

考虑怎么做：

对于加删边。我们记一个 bitset 类型的 g_{i,j} 表示加的边。

这个块初始时把当前黑边加入。后续操作直接在 g 上处理。复杂度 O(1)。

对于查询，朴素想法是直接做一个 bfs。当前边能走当且仅当「f 或 g」中这个位置为 1。

考虑用 bitset 优化 bfs。

::::info[关于 `bitset` 优化 bfs] 记 `bitset` 类型的 now 表示当前还未进队的点。将队头能转移到的点集（上文中的 $(f	g)_u）与 now 取交。为 1 代表能走。利用 `bitset` 中函数 `_Find_first()` 和 `_Find_next(p)` 枚举出现 1 的位置转移即可。时间复杂度 O(\frac{B^2}\omega)$。

总时间复杂度大约是（没仔细算） O(\frac{n^2+qB}\omega) 级别的，因为常数问题 B 取 250 较优。

::::warning[细节问题] 可能还需要考虑关键点所在连通块之间可能连多条边，一条边变白并不代表不能走，可能其他边能连过去。

因此在我的代码实现中用了 vis 数组和 map<pair<int,int>,int> 类型的 mp 来处理这个问题。

复杂度多了一只老哥。如果你足够聪明应该能想到更厉害的方法。 ::::

做完了。

AC 代码

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
    int k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=1e5+10,L=910;
struct que{int op,x,y;}ask[N];
int n,u[N],v[N];
bool ans[N];
bool cant[N],color[N];
namespace ksrj // 缩点，要改成 tarjan 也可以直接改的
{
    vector<pair<int,int>>e[N],e2[N];
    void add(int u,int v,int id){e[u].push_back({v,id});e2[v].push_back({u,id});}
    bool vis[N];
    vector<int>s;
    int cnt,num[N];
    void dfs1(int u)
    {
        vis[u]=true;
        for(auto [v,id]:e[u])if(!vis[v]&&!cant[id]&&color[id])dfs1(v); // 白边不能缩
        s.push_back(u);
    }
    void dfs2(int u)
    {
        num[u]=cnt;
        for(auto [v,id]:e2[u])if(!num[v]&&!cant[id]&&color[id])dfs2(v); // 白边不能缩
    }
    void kosaraju()
    {
        s.clear(),cnt=0;for(int i=1;i<=n;i++)num[i]=vis[i]=0;
        for(int i=1;i<=n;i++)if(!vis[i])dfs1(i);
        for(int i=n-1;i>=0;i--)if(!num[s[i]])cnt++,dfs2(s[i]);
    }
}
int S[N];
vector<int>G[N];int en[N];
bitset<L>f[L];
bitset<L>tmp[N];
int ID[N];
void toposort() // 维护可达性，记在 tmp 中
{
    queue<int>q;
    for(int i=1;i<=ksrj::cnt;i++)if(!en[i])q.push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v:G[u])
        {
            tmp[v]|=tmp[u];
            if(!(--en[v]))q.push(v);
        }
    }
}
bitset<L>g[L];
int len;
bool bfs(int s,int t) // bitset 优化 bfs
{
    if(s==t)return 1;
    bitset<L>now;now.set();
    queue<int>q;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        bitset<L>tmp=(now&(f[u]|g[u]));
        for(int v=tmp._Find_first();v<=len;v=tmp._Find_next(v))
        {
            if(v==t)return 1;
            q.push(v),now.reset(v);
        }
    }
    return 0;
}
int vis[N];
void clear(int l,int r) // 清空
{
    for(int i=l;i<=r;i++)if(ask[i].op==1)vis[ask[i].x]=cant[ask[i].x]=0;
    for(int i=1;i<=ksrj::cnt;i++)G[i].clear(),en[i]=0,tmp[i].reset();
    for(int i=1;i<=len;i++)f[i].reset(),g[i].reset(),ID[i]=0,S[i]=0;
}
map<pair<int,int>,int>mp;
void solve(int l,int r)
{
    for(int i=l;i<=r;i++)if(ask[i].op==1)cant[ask[i].x]=1; // cant 表示要在原图中挖去的边
    ksrj::kosaraju(),len=0;
    for(int i=l;i<=r;i++)
        if(ask[i].op==1)S[++len]=ksrj::num[u[ask[i].x]],S[++len]=ksrj::num[v[ask[i].x]];
        else S[++len]=ksrj::num[ask[i].x],S[++len]=ksrj::num[ask[i].y];
    sort(S+1,S+len+1),len=unique(S+1,S+len+1)-S-1; // 关键点弄出来
    for(int i=1;i<=len;i++)ID[S[i]]=i,tmp[S[i]].set(i);
    for(int u=1;u<=n;u++)
        for(auto [v,id]:ksrj::e[u])
        {
            if(cant[id]||!color[id]||ksrj::num[u]==ksrj::num[v])continue;
            G[ksrj::num[v]].push_back(ksrj::num[u]),en[ksrj::num[u]]++;
        }
    toposort();
    for(int i=1;i<=len;i++)f[i]=tmp[S[i]]; // 把连通块与关键点的关系变成关键点与关键点的关系
    for(int i=l;i<=r;i++)
    {
        if(!(ask[i].op==1&&color[ask[i].x]))continue;
        int U=ID[ksrj::num[u[ask[i].x]]];
        int V=ID[ksrj::num[v[ask[i].x]]];
        g[U].set(V); // 初始有的边
        if(!vis[ask[i].x])vis[ask[i].x]=1,mp[{U,V}]++;
    }
    for(int i=l;i<=r;i++) // 处理操作
        if(ask[i].op==1)
        {
            color[ask[i].x]^=1;
            int U=ID[ksrj::num[u[ask[i].x]]];
            int V=ID[ksrj::num[v[ask[i].x]]];
            if(!color[ask[i].x])mp[{U,V}]--; // 这就是 mp 的用法
            else mp[{U,V}]++;
            if(!mp[{U,V}])g[U].reset(V); // 更新边
            else g[U].set(V);
        }
        else ans[i]=bfs(ID[ksrj::num[ask[i].x]],ID[ksrj::num[ask[i].y]]); // 直接 bfs
    clear(l,r),mp.clear();
}
int main()
{
    n=in();int m=in(),q=in();
    for(int i=1;i<=m;i++)color[i]=1,u[i]=in(),v[i]=in(),ksrj::add(u[i],v[i],i);
    for(int i=1;i<=q;i++)
    {
        ask[i].op=in();
        if(ask[i].op==1)ask[i].x=in();
        else ask[i].x=in(),ask[i].y=in();
    }
    const int B=250;
    for(int i=1;i<=q;i+=B)solve(i,min(q,i+B-1));
    for(int i=1;i<=q;i++)if(ask[i].op==2)puts(ans[i]?"YES":"NO");
    return 0;
}

P11369 [Ynoi2024] 弥留之国的爱丽丝 题解

P11369 [Ynoi2024] 弥留之国的爱丽丝 题解

题意

思路

AC 代码

P11369 [Ynoi2024] 弥留之国的爱丽丝题解

P11369 [Ynoi2024] 弥留之国的爱丽丝题解