HDU 5333 Undirected Graph LCT+BIT Undirected Graph

112 阅读 0 评论 74 点赞

我是靠谱客的博主顺心裙子，这篇文章主要介绍HDU 5333 Undirected Graph LCT+BIT Undirected Graph，现在分享给大家，希望可以做个参考。

链接

Undirected Graph

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 184 Accepted Submission(s): 38

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

There is an undirected graph with

n vertices and

m edges. Then Yuta does

q operations on this graph. Each operation is described by two integers

L,R (1≤L≤R≤n) and can be split into three steps:

1. Delete all the edges which have at least one vertice outside the range

[L,R] .

2. Yuta wants you to tell him the number of connected component of the graph.

3. Restore the graph.

This task is too hard for Rikka to solve. Can you help her?

Input

There are at most 100 testcases and there are at least 97 testcases with

n,m,q≤1000 .

For each testcase, the first line contains three numbers

n,m,q (n,q≤105,m≤2×105) .

Then

m lines follow. Each line contains two numbers

ui,vi (1≤ui,vi≤105) which describe an edge of the graph.

Then

q lines follows. Each line contains two numbers

Li,Ri (1≤L≤R≤n) which describe an operation.

Output

For each operation you need print a single line with a single number - the answer of this operation.

Sample Input

复制代码

Sample Output

复制代码

Author

XJZX

Source

2015 Multi-University Training Contest 4

题意：

给定n个点m条边的无向图（有自环有重边） q个询问

对于某个询问 query : [l,r]

把所有的边形如 {u,v} u,v其中一个或者两个都不在区间[l,r]上的都删除，求此时残余图的连通分量数。

每个询问都是互相独立的，也就是每个询问都是从原图删除而来。

思路：

感觉很有道理的样子，写了一发，卡常数卡死人了。。

复制代码

#pragma comment(linker, "/STACK:1024000000")
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) pt(x / 10);
putchar(x % 10 + '0');
}
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 100;
const int inf = 10000000;
struct BIT {
int c[N], maxn;
void init(int n) {
maxn = n;
memset(c, 0, (10 + n) *sizeof(int));
}
int lowbit(int x) { return x&-x; }
int sum(int x) {
int ans = 0;
while (x)ans += c[x], x -= lowbit(x);
return ans;
}
int query(int l, int r) {
return sum(r) - sum(l - 1);
}
void change(int x, int val) {
while (x<=maxn)c[x] += val, x += lowbit(x);
}
}bit;
struct Node *null;
struct Node {
Node *fa, *ch[2];
int val;
int mi, min_id, id;
bool rev;
inline void put() {
printf("%d: fa:%d [%d,%d] val:%d ma:%d,%d rev:%dn", id, fa->id, ch[0]->id, ch[1]->id, val, mi, min_id, rev);
}
inline void clear(int _id) {
fa = ch[0] = ch[1] = null;
rev = 0;
id = _id;
mi = inf;
min_id = 0;
val = 0;
}
inline void push_up() {
if (this == null)return;
if (val) {
mi = min(id, min(ch[0]->mi, ch[1]->mi));
if (id <= min(ch[0]->mi, ch[1]->mi)) min_id = id;
else if (ch[0]->mi < min(ch[1]->mi, id	))min_id = ch[0]->min_id;
else min_id = ch[1]->min_id;
}
else
{
mi = min(ch[0]->mi, ch[1]->mi);
if (ch[0]->mi < ch[1]->mi)min_id = ch[0]->min_id;
else min_id = ch[1]->min_id;
}
}
inline void push_down() {
if (this == null)return;
if (rev) {
ch[0]->flip();
ch[1]->flip();
rev = 0;
}
}
inline void setc(Node *p, int d) {
ch[d] = p;
p->fa = this;
}
inline bool d() {
return fa->ch[1] == this;
}
inline bool isroot() {
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void flip() {
if (this == null)return;
swap(ch[0], ch[1]);
rev ^= 1;
}
inline void go() {//从链头开始更新到this
if (!isroot())fa->go();
push_down();
}
inline void rot() {
Node *f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c], c);
this->setc(f, !c);
if (ff->ch[cc] == f)ff->setc(this, cc);
else this->fa = ff;
f->push_up();
}
inline Node*splay() {
go();
while (!isroot()) {
if (!fa->isroot())
d() == fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node* access() {//access后this就是到根的一条splay，并且this已经是这个splay的根了
for (Node *p = this, *q = null; p != null; q = p, p = p->fa) {
p->splay()->setc(q, 1);
p->push_up();
}
return splay();
}
inline Node* find_root() {
Node *x;
for (x = access(); x->push_down(), x->ch[0] != null; x = x->ch[0]);
return x;
}
void make_root() {
access()->flip();
}
void cut() {//把这个点的子树脱离出去
access();
ch[0]->fa = null;
ch[0] = null;
push_up();
}
void cut(Node *x) {
if (this == x || find_root() != x->find_root())return;
else {
x->make_root();
cut();
}
}
void link(Node *x) {
if (find_root() == x->find_root())return;
else {
make_root(); fa = x;
}
}
};
Node pool[N], *tail;
Node *node[N];
void init(int n) {
tail = pool;
null = tail++;
null->clear(0);
for (int i = 1; i <= n; i++) {
node[i] = tail++;
node[i]->clear(i);
}
}
void debug(Node *x) {
if (x == null)return;
x->put();
debug(x->ch[0]);
debug(x->ch[1]);
}
int n, m, q;
struct BST {
int f[N];
void init(int n) { for (int i = 1; i <= n; i++)f[i] = i; }
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void Union(int u, int v) {
u = find(u); v = find(v);
if (u == v)return;
if (u > v)swap(u, v);
f[u] = v;
}
}cha;
void insert(int x, int y) {
//	puts("**===");	for (int i = 1; i <= max(x, y); i++)debug(node[i]), puts("");puts("");
if (cha.find(x) == cha.find(y)) {
node[y]->access();
//
puts("**");	for (int i = 1; i <= max(x, y); i++)debug(node[i]), puts("");puts("");
int id = node[y]->min_id;
if (y <= id)return;
//
printf("change id:%dn", id);
bit.change(id, -1);
node[id]->val--;
node[id]->cut(node[x]);
}
else cha.Union(x, y);
//	puts("---------");for (int i = 1; i <= x; i++)debug(node[i]), puts("");puts("");
bit.change(y, 1);
node[y]->make_root();
node[y]->val++;
node[y]->push_up();
node[y]->fa = node[x];
//	puts("@@@@@@");for (int i = 1; i <= x; i++)debug(node[i]), puts("");puts("");
}
int ans[N];
struct {
struct Edge {
int to, nex, id;
}edge[N << 1];
int head[N], edgenum;
void init(int n) {
memset(head, -1, (10 + n) *sizeof(int));
edgenum = 0;
}
void add(int u, int v, int id = 0) {
Edge E = { v, head[u], id};
edge[edgenum] = E;
head[u] = edgenum++;
}
}E, Q;
int main() {
while (~scanf("%d%d%d", &n,&m,&q)) {
E.init(n); Q.init(n); cha.init(n);
for (int i = 0, u, v;i < m; i++)
{
rd(u), rd(v);
if (u == v) {i--, m--;continue;}
if (u < v)E.add(v, u);else E.add(u, v);
}
for (int i = 0, u, v;i < q; i++) {
rd(u); rd(v);
Q.add(v, u, i);
}
bit.init(n);
init(n);
for (int i = 1; i <= n; i++)
{
for (int j = E.head[i]; ~j; j = E.edge[j].nex)
insert(i, E.edge[j].to);
for (int j = Q.head[i]; ~j; j = Q.edge[j].nex)
ans[Q.edge[j].id] = n - bit.query(Q.edge[j].to, i);
}
for (int i = 0; i < q; i++)	pt(ans[i]), puts("");
}
return 0;
}
/*
7 9 1
1 2
1 3
1 5
1 6
4 7
4 6
2 7
6 2
4 3
2 7
ans:3
*/

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
#pragma comment(linker, "/STACK:1024000000")
#include <iostream>
#include <fstream>
#include <string>
#include <time.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) pt(x / 10);
putchar(x % 10 + '0');
}
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 100;
const int inf = 10000000;
struct BIT {
int c[N], maxn;
void init(int n) {
maxn = n;
memset(c, 0, (10 + n) *sizeof(int));
}
int lowbit(int x) { return x&-x; }
int sum(int x) {
int ans = 0;
while (x)ans += c[x], x -= lowbit(x);
return ans;
}
int query(int l, int r) {
return sum(r) - sum(l - 1);
}
void change(int x, int val) {
while (x<=maxn)c[x] += val, x += lowbit(x);
}
}bit;
struct Node *null;
struct Node {
Node *fa, *ch[2];
int val;
int mi, min_id, id;
bool rev;
inline void put() {
printf("%d: fa:%d [%d,%d] val:%d ma:%d,%d rev:%dn", id, fa->id, ch[0]->id, ch[1]->id, val, mi, min_id, rev);
}
inline void clear(int _id) {
fa = ch[0] = ch[1] = null;
rev = 0;
id = _id;
mi = inf;
min_id = 0;
val = 0;
}
inline void push_up() {
if (this == null)return;
if (val) {
mi = min(id, min(ch[0]->mi, ch[1]->mi));
if (id <= min(ch[0]->mi, ch[1]->mi)) min_id = id;
else if (ch[0]->mi < min(ch[1]->mi, id	))min_id = ch[0]->min_id;
else min_id = ch[1]->min_id;
}
else
{
mi = min(ch[0]->mi, ch[1]->mi);
if (ch[0]->mi < ch[1]->mi)min_id = ch[0]->min_id;
else min_id = ch[1]->min_id;
}
}
inline void push_down() {
if (this == null)return;
if (rev) {
ch[0]->flip();
ch[1]->flip();
rev = 0;
}
}
inline void setc(Node *p, int d) {
ch[d] = p;
p->fa = this;
}
inline bool d() {
return fa->ch[1] == this;
}
inline bool isroot() {
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void flip() {
if (this == null)return;
swap(ch[0], ch[1]);
rev ^= 1;
}
inline void go() {//从链头开始更新到this
if (!isroot())fa->go();
push_down();
}
inline void rot() {
Node *f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c], c);
this->setc(f, !c);
if (ff->ch[cc] == f)ff->setc(this, cc);
else this->fa = ff;
f->push_up();
}
inline Node*splay() {
go();
while (!isroot()) {
if (!fa->isroot())
d() == fa->d() ? fa->rot() : rot();
rot();
}
push_up();
return this;
}
inline Node* access() {//access后this就是到根的一条splay，并且this已经是这个splay的根了
for (Node *p = this, *q = null; p != null; q = p, p = p->fa) {
p->splay()->setc(q, 1);
p->push_up();
}
return splay();
}
inline Node* find_root() {
Node *x;
for (x = access(); x->push_down(), x->ch[0] != null; x = x->ch[0]);
return x;
}
void make_root() {
access()->flip();
}
void cut() {//把这个点的子树脱离出去
access();
ch[0]->fa = null;
ch[0] = null;
push_up();
}
void cut(Node *x) {
if (this == x || find_root() != x->find_root())return;
else {
x->make_root();
cut();
}
}
void link(Node *x) {
if (find_root() == x->find_root())return;
else {
make_root(); fa = x;
}
}
};
Node pool[N], *tail;
Node *node[N];
void init(int n) {
tail = pool;
null = tail++;
null->clear(0);
for (int i = 1; i <= n; i++) {
node[i] = tail++;
node[i]->clear(i);
}
}
void debug(Node *x) {
if (x == null)return;
x->put();
debug(x->ch[0]);
debug(x->ch[1]);
}
int n, m, q;
struct BST {
int f[N];
void init(int n) { for (int i = 1; i <= n; i++)f[i] = i; }
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void Union(int u, int v) {
u = find(u); v = find(v);
if (u == v)return;
if (u > v)swap(u, v);
f[u] = v;
}
}cha;
void insert(int x, int y) {
//	puts("**===");	for (int i = 1; i <= max(x, y); i++)debug(node[i]), puts("");puts("");
if (cha.find(x) == cha.find(y)) {
node[y]->access();
//
puts("**");	for (int i = 1; i <= max(x, y); i++)debug(node[i]), puts("");puts("");
int id = node[y]->min_id;
if (y <= id)return;
//
printf("change id:%dn", id);
bit.change(id, -1);
node[id]->val--;
node[id]->cut(node[x]);
}
else cha.Union(x, y);
//	puts("---------");for (int i = 1; i <= x; i++)debug(node[i]), puts("");puts("");
bit.change(y, 1);
node[y]->make_root();
node[y]->val++;
node[y]->push_up();
node[y]->fa = node[x];
//	puts("@@@@@@");for (int i = 1; i <= x; i++)debug(node[i]), puts("");puts("");
}
int ans[N];
struct {
struct Edge {
int to, nex, id;
}edge[N << 1];
int head[N], edgenum;
void init(int n) {
memset(head, -1, (10 + n) *sizeof(int));
edgenum = 0;
}
void add(int u, int v, int id = 0) {
Edge E = { v, head[u], id};
edge[edgenum] = E;
head[u] = edgenum++;
}
}E, Q;
int main() {
while (~scanf("%d%d%d", &n,&m,&q)) {
E.init(n); Q.init(n); cha.init(n);
for (int i = 0, u, v;i < m; i++)
{
rd(u), rd(v);
if (u == v) {i--, m--;continue;}
if (u < v)E.add(v, u);else E.add(u, v);
}
for (int i = 0, u, v;i < q; i++) {
rd(u); rd(v);
Q.add(v, u, i);
}
bit.init(n);
init(n);
for (int i = 1; i <= n; i++)
{
for (int j = E.head[i]; ~j; j = E.edge[j].nex)
insert(i, E.edge[j].to);
for (int j = Q.head[i]; ~j; j = Q.edge[j].nex)
ans[Q.edge[j].id] = n - bit.query(Q.edge[j].to, i);
}
for (int i = 0; i < q; i++)	pt(ans[i]), puts("");
}
return 0;
}
/*
7 9 1
1 2
1 3
1 5
1 6
4 7
4 6
2 7
6 2
4 3
2 7
ans:3
*/