http://acm.hdu.edu.cn/contests/contest_show.php?cid=886

1004 - Discovery of Cycles

 

题意:给定一张无向图,边集中的每条边给了编号,多次询问,问只保留编号在 [l,r][l,r] 的边,是否有环。

只要判断环,可以考虑并查集。但是这里有多次询问,说明需要动态修改加边删边,所以要考虑 LCT

由于询问的端点可能抖动,所以即使离线后按照一维排序,另一维仍可能抖动,不能保证复杂度。

但是可以发现在一张已经有环的图上再加边并不会使得它没环,所以只要预处理出 i 作为左端点,第一次出现环时的右端点,再对于每个以 i 为左端点的询问,判断询问的右端点是否在预处理得到的右端点更右即可。

动态删边加边要用到 LCT,这里只需要一些基础操作,link 加边,cut 删边,findroot 用来找根判断是否已在同一棵树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e6 + 10;
const ll mod = 1e9 + 7;
struct LCT
{
#define lc c[x][0]
#define rc c[x][1]
int f[N], c[N][2], siz[N];
bool r[N];//区间翻转
inline void init(int n) {
for (int i = 0; i <= n; i++) {
f[i] = c[i][0] = c[i][1] = r[i] = 0;
siz[i] = 1;
}
}
inline bool nroot(int x) {
return c[f[x]][0] == x || c[f[x]][1] == x;
}
inline void rev(int x) { swap(lc, rc); r[x] ^= 1; }
inline void pushdown(int x) {
if (r[x]) {
if (lc)rev(lc);
if (rc)rev(rc);
r[x] = 0;
}
}
inline void update(int x) {
siz[x] = siz[lc] + siz[rc];
}
inline void rotate(int x) {
int y = f[x], z = f[y], k = c[y][1] == x, w = c[x][k ^ 1];
if (nroot(y))c[z][c[z][1] == y] = x;
if (w)f[w] = y;
c[x][k ^ 1] = y; c[y][k] = w;
f[y] = x; f[x] = z;
update(y), update(x);//先更新y
}
inline void pushall(int x) {
if (nroot(x))pushall(f[x]);
pushdown(x);
}
inline void splay(int x) {
pushall(x);
int y, z;
while (nroot(x)) {
y = f[x]; z = f[y];
if (nroot(y))rotate((c[y][0] == x && c[z][0] == y ? y : x));
rotate(x);
}
}
inline void access(int x) {
for (int y = 0; x; y = x, x = f[x])
splay(x), rc = y;
}
inline void makeroot(int x) { //原树
access(x); splay(x);
rev(x);
}
int findroot(int x) { //原树
access(x); splay(x);
while (lc)pushdown(x), x = lc;
splay(x);
return x;
}
inline void split(int x, int y) {
makeroot(x);
access(y); splay(y);
}
inline void link(int x, int y) {
makeroot(x);
if (findroot(y) != x)f[x] = y;
}
inline void cut(int x, int y) {
makeroot(x);
if (findroot(y) == x && f[y] == x && !c[y][0]) {
f[y] = c[x][1] = 0;
}
}
}lct;
int T;
int n, m, q;
int u[N], v[N];
int a[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u[i], &v[i]);
}
lct.init(n);
fill(a, a + m + 1, INF);
for (int l = 1, r = 1; l <= m; l++) {
while (r <= m) {
if (lct.findroot(u[r]) == lct.findroot(v[r])) {
a[l] = r;
break;
}
lct.link(u[r], v[r]);
r++;
}
lct.cut(u[l], v[l]);
}
int ans = 0;
while (q--) {
int l, r;
scanf("%d%d", &l, &r);
l = (l^ans) % m + 1;
r = (r^ans) % m + 1;
if (l > r)swap(l, r);
ans = (r >= a[l]);
puts(ans ? "Yes" : "No");
}
}
return 0;
}