题目链接：CodeChef GERALD07

大厨有一个无向图 $G$。顶点从 $1$ 到 $n$ 标号，边从 $1$ 到 $m$ 标号。

大厨有 $q$ 对询问 $L_i, R_i$。对于每对询问，大厨想知道当仅保留编号 $X$ 满足 $L_i \le X \le R_i$ 所在的边时，图 $G$ 中有多少了连通块。

注意数据可能包含自环和重边！

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10 ^ 3$，$1\le n, m, q \le 2\times 10 ^ 5$，$1\le L_i \le R_i \le M$，所有的 $n, m, q$ 的和均不超过 $2\times 10 ^ 5$。

Solution

首先我们把连通块个数转化一下：对于每个连通块维护生成树，假如所有生成树的总边数为 $x$，那么答案为 $n - x$。

离线

我们将询问按照 $R_i$ 为关键字从小到大排序。按顺序加入 $1$ 到 $m$ 的边，对于边 $(u, v)$ 考虑如下 $2$ 种情况：

• 点 $u, v$ 不连通：直接在加入这条边。
• 点 $u, v$ 已连通：删除路径 $u, v$ 上编号最小的边，再加入这条边。这个更新方法和「Codeforces 594D」REQ（题解）很相似。

最后考虑如何计算答案。很显然我们可以用 $\text{LCT}$ 维护这些生成树；边是否在生成树内可以用权值线段树维护。

时间复杂度：$\mathcal O((m + q)\log n)$。

在线

考虑一下强制在线的做法。

我们直接按照 $1$ 到 $m$ 的顺序加边，两种情况和上述离线做法一样讨论。而现在的问题是如何统计答案。

考虑一条边 $i$ 有贡献，也是 $2$ 种情况：

• 可以替换掉 $[1, i - 1]$ 中的一条边.
• 在加入之前的 $i - 1$ 条边后得到的生成树中，这条边的两个顶点不连通。

那么问题转化为：查询 $L$ 到 $R$ 中有多少条边可以替换掉 $1$ 到 $L - 1$ 内的边，再加上第二种情况的贡献。

我们可以用主席树统计答案。建立 $m$ 棵权值线段树，第 $i$ 棵线段树内的第 $j$ 个位置维护第 $1$ 到 $j$ 条边可以被多少条 $j + 1$ 到 $i$ 的边替换掉。为了方便查询，第二种情况的贡献统一加到线段树的第 $0$ 个位置。

对于每次询问 $L, R$，我们对第 $R$ 和 $L - 1$ 棵线段树的 $0$ 到 $L - 1$ 位置作差，再用 $n$ 减去这个值就是答案。

时间复杂度：$\mathcal O((m + q) \log n)$。

Code

篇幅限制，本文只给出在线解法的代码。

#include <cstdio>
#include <algorithm>
#include <cassert>

const int N = 2e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, q, E[N][2], f[N];

struct Node;
Node *null;

struct Node {
    Node *ch[2], *fa;
    int val, mn;
    bool rev;
    Node() {
        ch[0] = ch[1] = fa = null;
        val = mn = rev = 0;
    }
    bool get() {
        return fa->ch[1] == this;
    }
    bool isroot() {
        return fa->ch[0] != this && fa->ch[1] != this;
    }
    void reverse() {
        rev ^= 1, std::swap(ch[0], ch[1]);
    }
    void pushup() {
        mn = std::min(val, std::min(ch[0]->mn, ch[1]->mn));
    }
    void pushdown() {
        if (rev) {
            ch[0]->reverse();
            ch[1]->reverse();
            rev = 0;
        }
    }
} *a[N << 1];

struct LCT {
    void build(int n) {
        null = new Node();
        null->ch[0] = null->ch[1] = null->fa = null;
        null->val = null->mn = INF;
        for (int i = 1; i <= n; i++) {
            a[i] = new Node();
        }
    }
    void clear(int n) {
        delete null;
        for (int i = 1; i <= n; i++) {
            delete a[i];
        }
    }
    void pushtag(Node *x) {
        if (!x->isroot()) pushtag(x->fa);
        x->pushdown();
    }
    void rotate(Node *x) {
        Node *y = x->fa, *z = y->fa;
        int k = x->get();
        !y->isroot() && (z->ch[y->get()] = x), x->fa = z;
        y->ch[k] = x->ch[!k], x->ch[!k]->fa = y;
        x->ch[!k] = y, y->fa = x;
        y->pushup();
    }
    void splay(Node *x) {
        pushtag(x);
        while (!x->isroot()) {
            Node *y = x->fa;
            if (!y->isroot()) {
                rotate(x->get() == y->get() ? y : x);
            }
            rotate(x);
        }
        x->pushup();
    }
    void access(Node *x) {
        for (Node *y = null; x != null; x = (y = x)->fa) {
            splay(x), x->ch[1] = y, x->pushup();
        }
    }
    void makeroot(Node *x) {
        access(x), splay(x), x->reverse();
    }
    void split(Node *x, Node *y) {
        makeroot(x), access(y), splay(y);
    }
    void link(Node *x, Node *y) {
        split(x, y);
        x->fa = y;
    }
    void cut(Node *x, Node *y) {
        split(x, y);
        x->fa = y->ch[0] = null, y->pushup();
    }
};

struct Chairman {
    static const int M = 30 * N;
    int idx, rt[N], ls[M], rs[M], sum[M];
    void clear() {
        idx = 0;
    }
    void build(int &p, int l, int r) {
        p = ++idx, ls[p] = rs[p] = sum[p] = 0;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(ls[p], l, mid);
        build(rs[p], mid + 1, r);
    }
    void modify(int &p, int l, int r, int u, int x, int v) {
        p = ++idx, ls[p] = ls[u], rs[p] = rs[u], sum[p] = sum[u] + v;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(ls[p], l, mid, ls[u], x, v);
        } else {
            modify(rs[p], mid + 1, r, rs[p], x, v);
        }
    }
    int query(int p, int l, int r, int x, int y) {
        if (x <= l && r <= y) return sum[p];
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return query(ls[p], l, mid, x, y);
        } else if (x > mid) {
            return query(rs[p], mid + 1, r, x, y);
        } else {
            return query(ls[p], l, mid, x, mid) + query(rs[p], mid + 1, r, mid + 1, y);
        }
    }
} C;

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
    int T;
    for (scanf("%d", &T); T--; ) {
        scanf("%d%d%d", &n, &m, &q);
        LCT T;
        T.build(n + m);
        C.build(C.rt[0], 0, m);
        for (int i = 1; i <= n; i++) f[i] = i;
        for (int i = 1; i <= n + m; i++) {
            a[i]->val = (i > n ? i - n : INF);
        }
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            E[i][0] = u, E[i][1] = v;
            if (u == v) {
                C.rt[i] = C.rt[i - 1];
                continue;
            }
            if (find(u) == find(v)) {
                T.split(a[u], a[v]);
                int j = a[v]->mn;
                T.cut(a[E[j][0]], a[n + j]);
                T.cut(a[E[j][1]], a[n + j]);
                T.link(a[u], a[n + i]);
                T.link(a[v], a[n + i]);
                C.modify(C.rt[i], 0, m, C.rt[i - 1], j, 1);
            } else {
                f[find(u)] = find(v);
                T.link(a[u], a[n + i]);
                T.link(a[v], a[n + i]);
                C.modify(C.rt[i], 0, m, C.rt[i - 1], 0, 1);
            }
        }
        for (int i = 1; i <= q; i++) {
            int l, r;
            scanf("%d%d", &l, &r);
            int ans = C.query(C.rt[r], 0, m, 0, l - 1) - C.query(C.rt[l - 1], 0, m, 0, l - 1);
            printf("%d\n", n - ans);
        }
        T.clear(n + m);
        C.clear();
    }
    return 0;
}