4229: 选择

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 59 Solved: 36
[ Submit][ Status][ Discuss]

Description

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

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

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

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

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

Input

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

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

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

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

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

Output

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

Sample Input

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

Sample Output

Yes
Yes
No
No

HINT

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

Source

[ Submit][ Status][ Discuss]
将询问倒过来处理，就变成加边，查询两个点是否属于同一个边双 那么就要维护一个数据结构，支持动态加边，查询两个点是否属于同一个边双 可以使用LCT和并查集同时维护 并查集维护两个点是否属于同一个边双，如果是，用并查集压缩之 当新增一条边时，如果原来的两个点并不在同一棵LCT内，则普通的LCT加边操作 否则，假设这题边为(x,y)，将x换成根，Access(y)，splay(y) 给y的左儿子打上标记，要和y所在的边双合并就是 这种标记显然可以合并

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;const int maxn = 1E5 + 10;struct Query{int typ,x,y; Query(){}Query(int typ,int x,int y): typ(typ),x(x),y(y){}
}Q[maxn];struct E{int x,y; E(){}E(int x,int y): x(x),y(y){}bool operator < (const E &b) const{if (x < b.x) return 1;if (x > b.x) return 0;return y < b.y;}
}edgs[maxn];int n,m,q,tp,ch[maxn][2],rev[maxn],Mark[maxn],fa[maxn],pfa[maxn],ti[maxn],father[maxn],F[maxn],s[maxn];
bool bo[maxn],Ans[maxn];int getint()
{char ch = getchar(); int ret = 0;while (ch < '0' || '9' < ch) ch = getchar();while ('0' <= ch && ch <= '9')ret = ret*10 + ch - '0',ch = getchar();return ret;
}int getfa(int x) {return x == father[x] ? x : father[x] = getfa(father[x]);}
int getF(int x) {return x == F[x] ? x : F[x] = getF(F[x]);}void Connect(int x,int y)
{int fx = getfa(x),fy = getfa(y);if (fx == fy) return; father[fx] = fy;
}void Merge(int x,int y)
{if (!Mark[x]) Mark[x] = y;else Connect(Mark[x],y);
}void pushdown(int x)
{if (Mark[x]){for (int i = 0; i < 2; i++)if (ch[x][i]) Merge(ch[x][i],Mark[x]);Connect(x,Mark[x]); Mark[x] = 0;}if (rev[x]){for (int i = 0; i < 2; i++)if (ch[x][i]) rev[ch[x][i]] ^= 1;swap(ch[x][0],ch[x][1]); rev[x] = 0;}
}void rotate(int x)
{int y = fa[x],z = fa[y];pfa[x] = pfa[y]; pfa[y] = 0;int d = ch[y][0] == x ? 0 : 1;ch[y][d] = ch[x][d^1]; fa[ch[y][d]] = y;ch[x][d^1] = y; fa[y] = x; fa[x] = z;if (z) ch[z][ch[z][1] == y] = x;
}void splay(int x)
{for (int z = x; z; z = fa[z]) s[++tp] = z;while (tp) pushdown(s[tp--]);for (int y = fa[x]; y; rotate(x),y = fa[x])if (fa[y]) rotate((ch[y][0] == x) ^ (ch[fa[y]][0] == y) ? x : y);
}void Access(int x)
{for (int y = 0; x; y = x,x = pfa[x]){splay(x);if (ch[x][1]) fa[ch[x][1]] = 0,pfa[ch[x][1]] = x;ch[x][1] = y; if (y) pfa[y] = 0,fa[y] = x;}
}void ChangeRoot(int x) {Access(x); splay(x); rev[x] ^= 1;}void Add_edgs(int x,int y)
{int fx = getF(x),fy = getF(y);if (fx != fy){ChangeRoot(x); pfa[x] = y;Access(x); splay(x); F[fx] = fy;}else{fx = getfa(x); fy = getfa(y); Connect(fx,fy);ChangeRoot(x); Access(y); splay(y); Merge(ch[y][0],fx);}
}int getcom()
{char ch = getchar();while (ch != 'Z' && ch != 'P') ch = getchar();return ch == 'Z' ? 1 : 2;
}int main()
{n = getint(); m = getint(); q = getint();for (int i = 1; i <= m; i++){int x = getint(),y = getint();if (x > y) swap(x,y); edgs[i] = E(x,y);}sort(edgs + 1,edgs + m + 1);for (int i = 1; i <= q; i++){int typ = getcom(),x,y;x = getint(); y = getint();if (x > y) swap(x,y);if (typ == 1){int pos = lower_bound(edgs + 1,edgs + m + 1,E(x,y)) - edgs;Q[i] = Query(1,pos + ti[pos],0); bo[pos + ti[pos]] = 1; ++ti[pos];}else Q[i] = Query(2,x,y);}for (int i = 1; i <= n; i++) F[i] = father[i] = i;for (int i = 1; i <= m; i++)if (!bo[i]) Add_edgs(edgs[i].x,edgs[i].y);for (int i = q; i; i--)if (Q[i].typ == 1) Add_edgs(edgs[Q[i].x].x,edgs[Q[i].x].y);else{ChangeRoot(Q[i].x); ChangeRoot(Q[i].y);int fx = getfa(Q[i].x),fy = getfa(Q[i].y);Ans[i] = fx == fy ? 1 : 0;}for (int i = 1; i <= q; i++)if (Q[i].typ == 2){if (Ans[i]) puts("Yes");else puts("No");}return 0;
}