M_sea

洛谷4246 [SHOI2008]堵塞的交通
LuoguBZOJ分析动态图连通性的板子?当然可以用LCT维护删除时间最大生成树啦,但是我不太会qwq所以可以用离...
扫描右侧二维码阅读全文
09
2019/01

洛谷4246 [SHOI2008]堵塞的交通

Luogu

BZOJ

分析

动态图连通性的板子?

当然可以用LCT维护删除时间最大生成树啦,但是我不太会qwq

所以可以用离线的线段树分治氵过去qwq

按照$\mathrm{\color{black}{x}\color{red}{xz}}$的说法,具体是“将每条边的加入和删除时间加入到线段树中,所以在遍历到叶子节点时,那个时刻存在的边都已经在并查集上了,于是直接判断即可”。

然而并不用建线段树就可以分治。

然而正解是线段树,太长了不想打

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#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 MAXN=200000+10;

struct Edge { int u,v,st,ed; };
vector<Edge> e;
pair<int,int> q[MAXN],sta[MAXN];
map<int,int> G[MAXN];
int id[2][MAXN];
int n;
int cnt=0,q_num=0,top=0;
int root[MAXN],sz[MAXN];

inline int find(int x) { return x==root[x]?x:find(root[x]); }
inline void merge(int a,int b) {
    a=find(a),b=find(b); if (a==b) return;
    if (sz[a]>sz[b]) swap(a,b);
    root[a]=b,sz[b]+=sz[a],sta[++top]=make_pair(a,b);
}
inline void undo() {
    int x=sta[top].first,y=sta[top--].second;
    root[x]=x,sz[y]-=sz[x];
}

inline void solve(int l,int r,vector<Edge> e) {
    vector<Edge> L,R; int mid=(l+r)>>1,tmp=top;
    for (vector<Edge>::iterator it=e.begin();it!=e.end();++it) {
        if (it->st<=l&&r<=it->ed) merge(it->u,it->v);
        else {
            if (it->st<=mid) L.push_back(*it);
            if (it->ed>mid) R.push_back(*it);
        }
    }
    if (l==r)
        printf("%c\n",find(q[l].first)==find(q[l].second)?'Y':'N');
    else solve(l,mid,L),solve(mid+1,r,R);
    while (top>tmp) undo();
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) id[0][i]=++cnt,id[1][i]=++cnt;
    while (233) {
        char tmp[6]; scanf("%s",tmp);
        if (tmp[0]=='E') break;
        int r1=read()-1,c1=read(),r2=read()-1,c2=read();
        if (tmp[0]=='O') {
            e.push_back((Edge){id[r1][c1],id[r2][c2],q_num+1,-1});
            G[id[r1][c1]][id[r2][c2]]=G[id[r2][c2]][id[r1][c1]]=e.size()-1;
        }
        else if (tmp[0]=='C')
            e[G[id[r1][c1]][id[r2][c2]]].ed=q_num;
        else
            q[++q_num]=make_pair(id[r1][c1],id[r2][c2]);        
    }
    for (re vector<Edge>::iterator it=e.begin();it!=e.end();++it)
        if (it->ed==-1) it->ed=q_num;
    for (re int i=1;i<=(n<<1);++i) root[i]=i,sz[i]=1;
    solve(1,q_num,e);
    return 0;
}
最后修改:2019 年 01 月 11 日 10 : 36 PM

1 条评论

  1. smy

    您tql%%%%

发表评论