[CC-GERALD07]Chef and Graph Queries 题解
![[CC-GERALD07]Chef and Graph Queries 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180317d.jpg)
题目地址：CodeChef：Chef and Graph Queries | CodeChef
题目描述
大厨有一个无向图G。顶点从1到N标号，边从1到M标号。
大厨有Q对询问Li，Ri（1≤Li≤Ri≤M）。对于每对询问，大厨想知道当仅保留编号X满足Li≤X≤Ri所在的边时，图G中有多少连通块。
请帮助大厨回答这些询问。
输入输出格式
输入格式：
输入数据的第一行包含一个整数T，表示数据组数。对于每组数据，第一行包含三个整数N，M，Q。接下来的M行，每行包含两个整数Vi，Ui，依次表示一条无向边。接下来的Q行，每行包含两个整数Li，Ri，依次表示一组询问。
输出格式：
对于每组询问，输出对应的连通块数。
输入输出样例
输入样例#1：
2 3 5 4 1 3 1 2 2 1 3 2 2 2 2 3 1 5 5 5 1 2 1 1 1 1 1 1 1
输出样例#1：
2 1 3 1 1
说明
- 1≤T≤1000
- 1≤N, M, Q≤200000
- 1≤Ui, Vi≤N
- 1≤Li≤Ri≤M
- 数据保证所有N的和不超过200000。所有M的和不超过200000。所有Q的和不超过200000。
- 注意数据可能包含自环和重边！
题解
我们考虑一条边会对连通块产生什么影响，加一条边会合并某两个连通块，使得答案减少1，当然这仅当加这条边不会成环以及没有重边和自环的时候才会产生影响。因此我们考虑维护一个生成树，使得每加一条边，如果成环，删去该环中编号最小的边。该生成树上编号为[Li, Ri]的边有多少条，答案就是n-几。我们可以在逐条加边的过程中动态维护生成树以及生成树上的边编号计数。动态维护生成树可以用LCT做，而边编号计数则使用权值线段树。
这道题目的强制在线升级版可以看[BZOJ3514]Codechef MARCH14 GERALD07加强版 题解 | KSkun’s Blog。
LCT和线段树都是常数大的东西，还好跑过了。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <algorithm>
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int readint() {
register int res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 400005, INF = 1e9;
struct LCTNode {
int ch[2], fa, val, mn;
bool rev;
} lct[MAXN];
inline bool isleft(int p) {
return lct[lct[p].fa].ch[0] == p;
}
inline bool isroot(int p) {
register int fa = lct[p].fa;
return lct[fa].ch[0] != p && lct[fa].ch[1] != p;
}
inline void update(int p) {
register int ls = lct[p].ch[0], rs = lct[p].ch[1];
lct[p].mn = p;
if(lct[lct[ls].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[ls].mn;
if(lct[lct[rs].mn].val < lct[lct[p].mn].val) lct[p].mn = lct[rs].mn;
}
inline void reverse(int p) {
std::swap(lct[p].ch[0], lct[p].ch[1]);
lct[p].rev ^= 1;
}
inline void pushdown(int p) {
register int ls = lct[p].ch[0], rs = lct[p].ch[1];
if(lct[p].rev) {
if(ls) reverse(ls);
if(rs) reverse(rs);
lct[p].rev ^= 1;
}
}
int sta[MAXN], stop;
inline void pushto(int p) {
stop = 0;
while(!isroot(p)) {
sta[stop++] = p;
p = lct[p].fa;
}
pushdown(p);
while(stop) {
pushdown(sta[--stop]);
}
}
inline void rotate(int p) {
register bool t = !isleft(p); register int fa = lct[p].fa, ffa = lct[fa].fa;
lct[p].fa = ffa; if(!isroot(fa)) lct[ffa].ch[!isleft(fa)] = p;
lct[fa].ch[t] = lct[p].ch[!t]; lct[lct[fa].ch[t]].fa = fa;
lct[p].ch[!t] = fa; lct[fa].fa = p;
update(fa);
}
inline void splay(int p) {
pushto(p);
for(register int fa = lct[p].fa; !isroot(p); rotate(p), fa = lct[p].fa) {
if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
}
update(p);
}
inline void access(int p) {
for(register int q = 0; p; q = p, p = lct[p].fa) {
splay(p);
lct[p].ch[1] = q;
update(p);
}
}
inline void makert(int p) {
access(p);
splay(p);
reverse(p);
}
inline int findrt(int p) {
access(p);
splay(p);
while(lct[p].ch[0]) p = lct[p].ch[0];
return p;
}
inline void split(int u, int v) {
makert(u);
access(v);
splay(v);
}
inline void link(int u, int v) {
split(u, v);
lct[u].fa = v;
}
inline void cut(int u, int v) {
split(u, v);
if(lct[v].ch[0] != u || lct[lct[v].ch[0]].ch[1]) return;
lct[u].fa = lct[v].ch[0] = 0;
}
inline int query(int u, int v) {
split(u, v);
return lct[v].mn;
}
int sgt[MAXN << 2];
inline void insert(int o, int l, int r, int x, int v) {
if(l == r) {
sgt[o] += v;
return;
}
register int mid = (l + r) >> 1;
if(x <= mid) insert(o << 1, l, mid, x, v);
else insert((o << 1) | 1, mid + 1, r, x, v);
sgt[o] = sgt[o << 1] + sgt[(o << 1) | 1];
}
inline int query(int o, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) return sgt[o];
register int mid = (l + r) >> 1, res = 0;
if(ll <= mid) res += query(o << 1, l, mid, ll, rr);
if(rr > mid) res += query((o << 1) | 1, mid + 1, r, ll, rr);
return res;
}
int T, n, m, q, ut, vt, lst[MAXN], u[MAXN], v[MAXN], ans[MAXN];
struct Edge {
int u, v;
} edge[MAXN];
struct Query {
int l, r, id;
inline bool operator<(const Query &rhs) const {
return r < rhs.r;
}
} quer[MAXN];
int main() {
T = readint();
while(T--) {
n = readint(); m = readint(); q = readint();
// init
for(int i = 0; i <= n + m; i++) {
lct[i].ch[0] = lct[i].ch[1] = lct[i].fa = lct[i].mn = lct[i].rev = 0;
lct[i].val = INF;
}
memset(sgt, 0, sizeof(sgt));
// read
for(int i = 1; i <= m; i++) {
edge[i].u = readint(); edge[i].v = readint();
}
for(int i = 1; i <= q; i++) {
quer[i].l = readint(); quer[i].r = readint(); quer[i].id = i;
}
std::sort(quer + 1, quer + q + 1);
// work
int tot = n, ptr = 1;
for(int i = 1; i <= m; i++) {
int u = edge[i].u, v = edge[i].v;
if(u != v && findrt(u) == findrt(v)) {
int t = query(u, v), tv = lct[t].val;
cut(edge[tv].u, t);
cut(edge[tv].v, t);
insert(1, 1, m, tv, -1);
}
if(u != v) {
tot++;
lct[tot].mn = tot;
lct[tot].val = i;
link(u, tot);
link(v, tot);
insert(1, 1, m, i, 1);
}
while(ptr <= q && quer[ptr].r <= i) {
if(quer[ptr].r == i) {
ans[quer[ptr].id] = n - query(1, 1, m, quer[ptr].l, quer[ptr].r);
}
ptr++;
}
}
for(int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
}
return 0;
}
