[LOJ 121] 「离线可过」动态图连通性

题面

#121. 「离线可过」动态图连通性


Solution

这题我们考虑离线下来搞。离线之后,我们会发现,某条边会在某些询问区间中出现
考虑以询问的编号为下标建线段树,我们把每一条边出现的时间段全部加到线段树里面去
接下来,直接在线段树上跑dfs,每到一个区间,就把这个区间里面存的边通通在并查集中连上;每完成一个区间,就把这个区间连上的边通通取消(类似于回溯)。
这样搞,我们每次到一个叶子节点的时候,这个叶子节点代表的询问上所要连的边一定已经全部连上了,直接在并查集中查询即可。
因为我们这里有撤销(回溯)操作,因此必需使用按秩合并的并查集。我们只需要开一个栈,把每次修改的fa的节点记录下来即可完成撤销的操作。

时间复杂度$O(nlog^2n)$?
反正是$O(能过)$

就酱,我们又切掉一道题啦φ(>ω<*)


Code

正解

//LOJ #121. 「离线可过」动态图连通性
//Mar,21st,2019
//线段树分治离线维护动态图连通性
#include<iostream>
#include<cstdio>
#include<vector>
#include<ctime>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=5000+100;
const int M=500000+100;
int n,m,q,p,ans[M];
inline int GetID(int s,int t)
{
    if(s>t) swap(s,t);
    return (s-1)*(n+1)+t;
}
struct UnF
{   
    int size[N],fa[N],mstack[M],top;
    void Init()
    {
        for(int i=1;i<=n;i++)
            size[i]=1;
    }
    int FindFather(int x)
    {
        if(fa[x]==0) return x;
        return FindFather(fa[x]);
    }
    void Link(int x,int y)
    {
        mstack[++top]=0;
        int fa_x=FindFather(x),fa_y=FindFather(y);
        if(size[fa_x]>size[fa_y]) 
            swap(x,y),swap(fa_x,fa_y);
        if(fa_x==fa_y) return;
        mstack[top]=fa_x;   
        fa[fa_x]=fa_y,size[fa_y]+=size[fa_x];
    }
    int Query(int x,int y)
    {
        if(FindFather(x)==FindFather(y)) return true;
        return false;
    }
    void Undo()
    {
        if(mstack[top]==0)
        {
            top--;
            return;
        }
        size[fa[mstack[top]]]-=size[mstack[top]];
        fa[mstack[top]]=0;
        top--;
    }
}unf;
struct OP
{
    int s,t,id;
}op[M],op2[M];
struct SegmentTree
{
    #define mid ((now_l+now_r)>>1)
    #define lson (now<<1)
    #define rson (now<<1|1)
    vector <int> e[M<<2];
    void Insert(int l,int r,int x,int now,int now_l,int now_r)
    {
        if(now_l>=l and now_r<=r)
        {
            //cerr<<now_l<<" "<<now_r<<endl;
            e[now].push_back(x);
            return;
        }
        if(l<=mid) Insert(l,r,x,lson,now_l,mid);
        if(r>mid) Insert(l,r,x,rson,mid+1,now_r);
    }
    void dfs(int now,int now_l,int now_r)
    {
        if(now_l>now_r) return;
        for(int i=0;i<int(e[now].size());i++)
        {
            //cerr<<now_l<<" "<<now_r<<" "<< e[now][i]%(n+1)<<" "<<e[now][i]/(n+1)+1<<endl;
            unf.Link(e[now][i]%(n+1),e[now][i]/(n+1)+1);
        }
        if(now_l==now_r)
            ans[now_l]=unf.Query(op[now_l].s,op[now_l].t);
        else
        {
            dfs(lson,now_l,mid);
            dfs(rson,mid+1,now_r);
        }
        for(int i=0;i<int(e[now].size());i++)
            unf.Undo();
    }
    #undef mid
    #undef lson
    #undef rson
}sgt;
int last[N*N];
int main()
{
    freopen("121.in","r",stdin);
    freopen("121.out","w",stdout);

    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int top=read(),s=read(),t=read();
        if(top==0)
            last[GetID(s,t)]=q+1;
        else if(top==1)
        {
            op2[++p].s=last[GetID(s,t)],op2[p].t=q,op2[p].id=GetID(s,t);
            last[GetID(s,t)]=0;
        }
        else
            op[++q].s=s,op[q].t=t;
    }
    for(int i=1;i<=(n+1)*(n+1);i++)
        if(last[i]!=0)
            op2[++p].s=last[i],op2[p].t=q,op2[p].id=i;

    for(int i=1;i<=p;i++)
        if(op2[i].s<=op2[i].t)
            sgt.Insert(op2[i].s,op2[i].t,op2[i].id,1,1,q);
    unf.Init();
    sgt.dfs(1,1,q);

    for(int i=1;i<=q;i++)
        if(ans[i]==0)
            printf("N\n");
        else
            printf("Y\n");
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注