BZOJ4229选择——LCT+并查集+离线(LCT动态维护边双连通分量)-白红宇

BZOJ4229选择——LCT+并查集+离线(LCT动态维护边双连通分量)

阅读量：6623 次

发布时间：2019-06-25

本文共 2892 字，大约阅读时间需要 9 分钟。

题目描述

现在，我想知道自己是否还有选择。

给定n个点m条边的无向图以及顺序发生的q个事件。

每个事件都属于下面两种之一：

1、删除某一条图上仍存在的边

2、询问是否存在两条边不相交的路径可以从点u出发到点v

输入

第一行三个整数n,m,q

接下来m行，每行两个整数u,v，表示u和v之间有一条边

接下来q行，每行一个大写字母o和2个整数u、v，依次表示按顺序发生的q个事件：

当o为’Z’时，表示删除一条u和v之间的边

当o为’P’时，表示询问是否存在两条边不相交的路径可以从点u出发到点v

输出

对于每组询问，如果存在，输出Yes,否则输出No

样例输入

7 8 7

1 2

1 3

1 4

2 3

3 4

3 7

7 4

5 6

Z 1 4

P 1 3

P 2 4

Z 1 3

P 1 3

Z 6 5

P 5 6

样例输出

Yes

提示

对于全部数据，max(n,m,q)<=100000

只有删边没有加边，删边并不好做，我们将询问离线倒过来做，这样删边就变成了加边。

之后题目就转化成了。

#include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #define pr pair
                  
                   #define ll long longusing namespace std;int g[100010];int fa[100010];int f[100010];int s[100010][2];int st[100010];int r[100010];int n,m,p;int opt;int x,y;set
                   
                    b;char ch[10];int ans[100010];struct miku{ int opt; int x,y;}q[100010];struct Miku{ int x,y;}a[100010];int find(int x){ if(fa[x]==x) { return x; } return fa[x]=find(fa[x]);}int judge(int x){ if(g[x]==x) { return x; } return g[x]=judge(g[x]);}int is_root(int rt){ return rt!=s[find(f[rt])][0]&&rt!=s[find(f[rt])][1];}int get(int rt){ return rt==s[find(f[rt])][1];}void pushdown(int rt){ if(r[rt]) { swap(s[rt][0],s[rt][1]); r[s[rt][0]]^=1; r[s[rt][1]]^=1; r[rt]^=1; }}void rotate(int rt){ int fa=find(f[rt]); int anc=find(f[fa]); int k=get(rt); if(!is_root(fa)) { s[anc][get(fa)]=rt; } s[fa][k]=s[rt][k^1]; f[s[fa][k]]=fa; s[rt][k^1]=fa; f[fa]=rt; f[rt]=anc;}void splay(int rt){ int top=0; st[++top]=rt; for(int i=rt;!is_root(i);i=find(f[i])) { st[++top]=find(f[i]); } for(int i=top;i>=1;i--) { pushdown(st[i]); } for(int fa;!is_root(rt);rotate(rt)) { if(!is_root(fa=find(f[rt]))) { rotate(get(fa)==get(rt)?fa:rt); } }}void access(int rt){ for(int x=0;rt;x=rt,rt=find(f[rt])) { splay(rt); s[rt][1]=x; }}void reverse(int rt){ access(rt); splay(rt); r[rt]^=1;}void dfs(int x,int rt){ fa[x]=rt; if(s[x][0]) { dfs(s[x][0],rt); } if(s[x][1]) { dfs(s[x][1],rt); }}void link(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy) { if(judge(fx)!=judge(fy)) { reverse(fx); f[fx]=fy; g[g[fx]]=g[fy]; } else { reverse(fx); access(fy); splay(fy); dfs(fy,fy); s[fy][0]=0; } }}int main(){ scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++) { fa[i]=g[i]=i; } for(int i=1;i<=m;i++) { scanf("%d%d",&a[i].x,&a[i].y); } for(int i=1;i<=p;i++) { scanf("%s",ch); scanf("%d%d",&q[i].x,&q[i].y); if(ch[0]=='Z') { q[i].opt=1; b.insert(make_pair(min(q[i].x,q[i].y),max(q[i].x,q[i].y))); } } for(int i=1;i<=m;i++) { if(b.find(make_pair(min(a[i].x,a[i].y),max(a[i].x,a[i].y)))==b.end()) { link(a[i].x,a[i].y); } } for(int i=p;i>=1;i--) { if(q[i].opt) { link(q[i].x,q[i].y); } else { ans[i]=(find(q[i].x)==find(q[i].y)); } } for(int i=1;i<=p;i++) { if(!q[i].opt) { printf(ans[i]?"Yes\n":"No\n"); } }}