LOJ121 「离线可过」动态图连通性

LOJ

分析

线段树分治板子题?

考虑每条边出现的时间都是若干段区间。我们以时间为下标建一棵线段树,然后在每条边出现的区间挂上这条边。然后我们把询问挂在叶节点上。

DFS 这棵线段树,每次到一个节点后就把这个节点上挂的所有边连上。这样子到叶节点时该时间点所有的边都已经连上了,直接询问是否连通即可。

这个过程中用一个可撤销并查集维护连通性即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10,M=500000+10;

int n,m;

int fa[N],rnk[N]; pair<int,int> sta[N]; int top=0;
inline int find(int x) { return x==fa[x]?x:find(fa[x]); }
inline void merge(int x,int y) {
    x=find(x),y=find(y);
    if (x==y) return;
    if (rnk[x]<rnk[y]) swap(x,y);
    fa[y]=x,sta[++top]=make_pair(y,rnk[y]);
    if (rnk[x]==rnk[y]) sta[++top]=make_pair(x,++rnk[x]);
}
inline void undo(int pos) {
    while (top>pos) {
        fa[sta[top].first]=sta[top].first;
        rnk[sta[top].first]=sta[top].second;
        --top;
    }
}

struct query { int x,y,t,id; } q[M],lq[M],rq[M];
int tim[N][N],ans[M],qcnt=0;

#define ls (o<<1)
#define rs (o<<1|1)
vector<pair<int,int> > vec[M<<2];
inline void modify(int o,int l,int r,int ql,int qr,pair<int,int> e) {
    if (ql<=l&&r<=qr) { vec[o].push_back(e); return; }
    int mid=(l+r)>>1;
    if (ql<=mid) modify(ls,l,mid,ql,qr,e);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,e);
}
inline void solve(int o,int l,int r,int ql,int qr) {
    if (ql>qr) return;
    int tmp=top;
    for (re auto i:vec[o]) merge(i.first,i.second);
    if (l==r) {
        for (re int i=ql;i<=qr;++i)
            ans[q[i].id]=find(q[i].x)==find(q[i].y);
        return;
    }
    int mid=(l+r)>>1,lcnt=0,rcnt=0;
    for (re int i=ql;i<=qr;++i)
        q[i].t<=mid?lq[++lcnt]=q[i]:rq[++rcnt]=q[i];
    for (re int i=1;i<=lcnt;++i) q[ql+i-1]=lq[i];
    for (re int i=1;i<=rcnt;++i) q[ql+lcnt+i-1]=rq[i];
    solve(ls,l,mid,ql,ql+lcnt-1);
    solve(rs,mid+1,r,ql+lcnt,qr);
    undo(tmp);
}
#undef ls
#undef rs

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int op=read(),x=read(),y=read();
        if (x>y) swap(x,y);
        if (op==0) tim[x][y]=i;
        if (op==1) modify(1,1,m,tim[x][y],i,make_pair(x,y)),tim[x][y]=0;
        if (op==2) q[++qcnt]=(query){x,y,i,qcnt};
    }
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;++j)
            if (tim[i][j]) modify(1,1,m,tim[i][j],m,make_pair(i,j));
    for (re int i=1;i<=n;++i) fa[i]=i,rnk[i]=1;
    solve(1,1,m,1,qcnt);
    for (re int i=1;i<=qcnt;++i) puts(ans[i]?"Y":"N");
    return 0;
}
最后修改:2019 年 10 月 21 日 08 : 51 AM

1 条评论

  1. xgzc

    其实是LCT板子题(

发表评论