题目概述

CF GYM103687K

解题报告

科技题过于困难。

考虑离线，如果我们把询问分成若干个长度为 $BLK$ 的块，那么块中最多涉及到 $BLK$ 条边，$2BLK$ 个点。这样就可以大大减小用bitset维护传递闭包的开销。

对于每个块，我们先考虑不使用块中的边建出图 $A$ ，由于这题没有保证是个DAG，所以我们需要对这张图进行缩点，得到图 $B$ 。然后在 $B$ 中拓扑bitset求出 $f_x$ 表示 $x$ 能到达的块中的点的集合。

接下来对于每个块中询问 $i$ ，如果 $u_i\to v_i$ 在 $B$ 中不可行，我们就考虑加入到 $i$ 为止的块中的黑边，得到每个点的出边集合 $S_x$ ，但这样图就可能不是一个DAG了，不过由于我们只需要查询 $u_i\to v_i$ ，因此直接考虑从 $u_i$ 开始做BFS，只记录块中的点，查询是否可以到 $v_i$ 。具体地说，从 $u_i$ 开始，找 $f_{u_i}$ 以及 $S_{u_i}$ 中的点进行遍历，以此类推。为了节省复杂度，我们再用一个bitset记录哪些点访问过了，这样就可以在BFS时避免掉重复遍历。

我们来分析一下复杂度，对于建图 $B$ 的部分，我们需要 $O(n+m+{(n+m)BLK\over w})$ ，对于一次查询，我们需要 $O(BLK+{BLK^2\over w})$ 。因此总复杂度是 $O({q\over BLK}(n+m+{(n+m)BLK\over w})+q(BLK+{BLK^2\over w}))$ 。

合并一下得到 $O({q(n+m)\over w}+q({n+m\over BLK}+BLK+{BLK^2\over w}))$ ，理论上取 $BLK=w$ 比较好，但是实际上由于前面那一部分有Tarjan以及拓扑常数比较大，因此可以尽量把 $BLK$ 取大一些。

示例程序

调参发现我的代码取 $BLK=500$ 左右跑得比较快🤪。

#include<cstdio>
#include<cctype>
#include<bitset>
#include<algorithm>
using namespace std;
const int maxn=50000,maxm=100000,maxq=100000,BLK=500,maxk=BLK<<1;

int n,m,Q,X[maxm+5],Y[maxm+5];bool ok[maxm+5];
struct Query {int tp,x,y;} q[maxq+5];
int E,lnk[maxn+5],nxt[maxm+5],to[maxm+5];
int ti,vis[maxm+5],cnt,p[maxk+5],ID[maxn+5];
int dfn[maxn+5],low[maxn+5],top,stk[maxn+5];bool instk[maxn+5];
int SCC[maxn+5],que[maxn+5],D[maxn+5];
bitset<maxk> f[maxn+5],S[maxk+5],use,now;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void Tarjan(int x){
    dfn[x]=low[x]=++dfn[0];stk[++top]=x;instk[x]=true;
    for (int j=lnk[x],u;j;j=nxt[j])
        if (!dfn[u=to[j]]) Tarjan(u),low[x]=min(low[x],low[u]); else
        if (instk[u]) low[x]=min(low[x],dfn[u]);
    if (dfn[x]==low[x]){
        int y=stk[top--];
        while (y!=x) {SCC[y]=x;instk[y]=false;y=stk[top--];}
        SCC[y]=x;instk[y]=false;
    }
}
void Topo(){
    int Head=0,Tail=0;
    for (int i=1;i<=n;i++) if (i==SCC[i] && !D[i]) que[++Tail]=i;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x];j;j=nxt[j]){
            f[to[j]]|=f[x];
            if (!(--D[to[j]])) que[++Tail]=to[j];
        }
}
bool Ask(int s,int t,int L,int R){
    if (s==t || f[p[s]][t]) return true;
    use=0;for (int i=0;i<cnt;i++) S[i]=0,use[i]=1;
    for (int i=L;i<=R;i++)
        if (q[i].tp==1 && ok[q[i].x]){
            int x=SCC[X[q[i].x]],y=SCC[Y[q[i].x]];
            if (x!=y) S[ID[x]][ID[y]]=1;
        }
    int Head=0,Tail=0;
    que[++Tail]=s;use[s]=0;
    while (Head!=Tail){
        int x=que[++Head];
        now=(f[p[x]]|S[x])&use;
        for (int i=now._Find_first();i<maxk;i=now._Find_next(i)){
            if (i==t) return true;
            que[++Tail]=i;use[i]=0;
        }
    }
    return false;
}
void Solve(int L,int R){
    ti++;for (int i=L;i<=R;i++) if (q[i].tp==1) vis[q[i].x]=ti;
    E=cnt=0;for (int i=1;i<=n;i++) lnk[i]=dfn[i]=D[i]=0,f[i]=0;

    for (int i=1;i<=m;i++) if (vis[i]<ti && ok[i]) Add(X[i],Y[i]);
    dfn[0]=0;for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
    E=0;for (int i=1;i<=n;i++) lnk[i]=0;
    for (int i=1;i<=m;i++)
        if (vis[i]<ti && ok[i] && SCC[X[i]]!=SCC[Y[i]])
            Add(SCC[Y[i]],SCC[X[i]]),D[SCC[X[i]]]++;

    for (int i=L;i<=R;i++)
        if (q[i].tp==1) p[cnt++]=SCC[X[q[i].x]],p[cnt++]=SCC[Y[q[i].x]];
        else p[cnt++]=SCC[q[i].x],p[cnt++]=SCC[q[i].y];
    sort(p,p+cnt);cnt=unique(p,p+cnt)-p;
    for (int i=0;i<cnt;i++) ID[p[i]]=i,f[p[i]][i]=1;
    Topo();

    for (int i=L;i<=R;i++)
        if (q[i].tp==1) ok[q[i].x]^=1;
        else puts(Ask(ID[SCC[q[i].x]],ID[SCC[q[i].y]],L,R)?"YES":"NO");
}
int main(){
    readi(n);readi(m);readi(Q);
    for (int i=1;i<=m;i++) readi(X[i]),readi(Y[i]),ok[i]=true;
    for (int i=1;i<=Q;i++){
        readi(q[i].tp);readi(q[i].x);
        if (q[i].tp==2) readi(q[i].y);
    }
    for (int i=1;i<=Q;i+=BLK) Solve(i,min(i+BLK-1,Q));
    return 0;
}