hihocoder1629_Graph

题目传送门
题意: 给你一个带标号的无向图,有$q$次询问,每次询问区间$[L,R]$内有多少对点联通并且该路径上所有点都在这个区间内.

按端点从小到大的顺序加边,每条边加两次,然后能得到一个边序列,同时能处理出每个点所属的边的区间$[l_{i},r_{i}]$,对于一个询问$[L,R]$,即询问边序列上区间$[l_{L},r_{R}]$内两个端点都在$[L,R]$内的那些边组成的图的答案.
然后把这个边序列分块,用类似莫队的思想处理询问,只是把减操作变成了还原操作,用按秩合并的并查集维护联通块个数即可.

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
//created by missever
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
const int b_size = 333;
P p[maxn];
vector<int> g[maxn];
int l[maxn],r[maxn],id[maxn],lim[maxn];
LL ans[maxn];
struct que {
int l,r,id;
} fq[maxn];
bool cmp(const que &a,const que &b) {
if(id[l[a.l]] == id[l[b.l]]) return r[a.r] < r[b.r];
else return id[l[a.l]] < id[l[b.l]];
}
struct union_find {
int f[maxn],rk[maxn],num[maxn],tot;
P res[maxn];
LL ans;
void init(int n) {
for(int i = 0; i <= n; i++) f[i] = i,rk[i] = num[i] = 1;
ans = tot = 0;
}
int ff(int x) {
while(f[x] != x) x = f[x];
return x;
}
void do_union(int x,int y) {
x = ff(x);
y = ff(y);
if(x == y) return;
if(rk[x] < rk[y]) swap(x,y);
res[tot++] = P(y,rk[x]);
f[y] = x;
ans += 1LL * num[x] * num[y];
num[x] += num[y];
rk[x] = max(rk[x],rk[y] + 1);
}
void back(int m) {
int x,y;
while(tot > m) {
tot--;
y = res[tot].fi;
x = f[y];
rk[x] = res[tot].se;
num[x] -= num[y];
ans -= 1LL * num[x] * num[y];
f[y] = y;
}
}
} uf;
void solve() {
int n,m,q,i,j,pre,k,x,y;
scanf("%d%d%d",&n,&m,&q);
for(i = 1; i <= n; i++) g[i].clear();
for(i = 0; i < m; i++) {
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(i = 1,m = -1;i <= n; i++) {
l[i] = m + 1;
for(auto v:g[i]) {
if(v > i) p[++m] = P(i,v);
else p[++m] = P(v,i);
lim[m] = i;
}
r[i] = m;
}
for(i = j = 0,k = 1;i <= m; i++) {
if(++j == b_size) k++,j = 0;
id[i] = k;
}
for(i = 0; i < q; i++) {
scanf("%d%d",&fq[i].l,&fq[i].r);
fq[i].id = i;
}
sort(fq,fq + q,cmp);
i = 0;
while(i < q) {
k = id[l[fq[i].l]];
uf.init(n);
pre = 0;
x = y = min(k * b_size,m + 1);
while(i < q && id[l[fq[i].l]] == k) {
if(id[r[fq[i].r]] <= k) {
for(j = l[fq[i].l];j <= r[fq[i].r]; j++) {
if(fq[i].l <= p[j].fi && p[j].se <= fq[i].r) uf.do_union(p[j].fi,p[j].se);
}
} else {
while(x <= r[fq[i].r]) {
if(lim[y] <= p[x].fi && p[x].se <= fq[i].r) uf.do_union(p[x].fi,p[x].se);
x++;
}
pre = uf.tot;
for(j = l[fq[i].l];j < y; j++) {
if(fq[i].l <= p[j].fi && p[j].se <= fq[i].r) uf.do_union(p[j].fi,p[j].se);
}
}
ans[fq[i++].id] = uf.ans;
uf.back(pre);
}
}
for(i = 0;i < q; i++) printf("%lld\n",ans[i]);
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t;
scanf("%d",&t);
while(t--) solve();
return 0;
}