问题分析

本题需要处理动态图连通性问题，并回答在特定时间点、特定位置发生山体滑坡时的最小基站数量。

关键观察

山体滑坡将图分割为左右两部分，连接两部分的边被破坏

最小基站数量 = 连通分量数量

问题转化为：在特定时间点的图状态中，删除跨越滑坡位置的边后，求连通分量数

核心算法：分块 + 可撤销并查集

算法框架

使用操作分块和可撤销并查集来高效处理动态图和多个查询。

数据结构设计

struct node {
    int i, u, v;  // 边信息
} a[maxn];

struct que {
    int w, p, i;  // 查询：时间w，滑坡位置p，查询编号i
} b[maxn];

int fa[maxn], rnk[maxn], top, cnt;
pair<int *, int> stk[maxn << 1];  // 可撤销并查集的栈
可撤销并查集实现

可撤销并查集实现

inline int find(int x) {
    while (x != fa[x]) {
        x = fa[x];
    }
    return x;
}

inline void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    
    ++cnt;  // 连通分量减少
    if (rnk[x] <= rnk[y]) {
        stk[++top] = mkp(fa + x, fa[x]);
        fa[x] = y;
        if (rnk[x] == rnk[y]) {
            stk[++top] = mkp(rnk + y, rnk[y]);
            ++rnk[y];
        }
    } else {
        stk[++top] = mkp(fa + y, fa[y]);
        fa[y] = x;
    }
}

算法流程

1.预处理阶段

void work() {
    // 按滑坡位置排序查询
    sort(b + 1, b + q + 1, [&](const que &a, const que &b) {
        return a.p < b.p;
    });
    
    // 离散化边
    sort(e + 1, e + tot + 1);
    tot = unique(e + 1, e + tot + 1) - e - 1;
    
    // 分块处理查询
    for (int k = 1; k <= (m + B - 1) / B; ++k) {
        int l = (k - 1) * B + 1, r = min(k * B, m);
        // 处理当前块的查询
    }
}

2.分块处理

// 初始化并查集
for (int i = 1; i <= n; ++i) {
    fa[i] = i;
    rnk[i] = 1;
}

// 处理当前块的每个查询
for (int i : vq[k]) {
    // 应用永久边（滑坡位置前的边）
    while (j <= tot && e[j].scd <= b[i].p) {
        if (vis[j] && !mk[j]) {  // 边存在且不在当前块
            merge(e[j].fst, e[j].scd);
        }
        ++j;
    }
    
    // 临时应用当前块的边
    for (int j = l; j <= b[i].w; ++j) {
        vis[a[j].i] ^= 1;  // 切换边状态
    }
    
    // 计算临时边的影响
    for (int j = 1; j <= tt; ++j) {
        if (vis[c[j]] && e[c[j]].scd <= b[i].p) {
            merge(e[c[j]].fst, e[c[j]].scd);
        }
    }
    
    // 记录答案并撤销临时操作
    ans[b[i].i] += cnt;
    while (top > ltop) {  // 撤销临时合并
        *stk[top].fst = stk[top].scd;
        --top;
    }
}

3.对称处理

由于滑坡可能发生在任意位置，需要从两个方向处理：

// 第一次处理：从左到右
work();

// 第二次处理：从右到左（通过坐标变换）
for (int i = 1; i <= q; ++i) {
    b[i].p = n - b[i].p;
}
for (int i = 1; i <= m; ++i) {
    a[i].u = n - a[i].u + 1;
    a[i].v = n - a[i].v + 1;
    swap(a[i].u, a[i].v);
}
work();

4.最终答案计算

for (int i = 1; i <= q; ++i) {
    writeln(n - ans[i]);  // 连通分量数 = n - 合并次数
}

复杂度分析

预处理：$O(m \log m)$ 排序和离散化

每个块：$O(B + \frac{m}{B} \cdot n \alpha(n))$ 并查集操作

总复杂度：$O(m \sqrt{m} \alpha(n))$，其中 $\alpha(n)$ 是并查集复杂度

空间复杂度：$O(m + n)$

算法优势

分块优化：将操作分块，减少重复计算

可撤销并查集：支持临时操作的撤销

对称处理：统一处理左右两个方向的滑坡

离线处理：批量处理查询，提高缓存效率

总结

本题通过操作分块和可撤销并查集的巧妙结合，解决了动态图连通性查询的难题。算法充分利用了查询的离线特性，通过分块平衡预处理和查询的时间复杂度，在 $10^5$ 的数据规模下仍能高效运行。

AC代码

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

namespace IO {
const int maxn = 1 << 20;

char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;

inline char gc() {
    return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
}

template<typename T = int>
inline T read() {
    char c = gc();
    T x = 0;
    bool f = 0;

    while (c < '0' || c > '9') {
        f |= (c == '-');
        c = gc();
    }

    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = gc();
    }

    return f ? ~(x - 1) : x;
}

inline void flush() {
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
}

struct Flusher {
    ~Flusher() {
        flush();
    }
} AutoFlush;

inline void pc(char ch) {
    if (oS == obuf + maxn) {
        flush();
    }

    *oS++ = ch;
}

template<typename T>
inline void write(T x) {
    static char stk[64], *tp = stk;

    if (x < 0) {
        x = ~(x - 1);
        pc('-');
    }

    do {
        *tp++ = x % 10;
        x /= 10;
    } while (x);

    while (tp != stk) {
        pc((*--tp) | 48);
    }
}

template<typename T>
inline void writesp(T x) {
    write(x);
    pc(' ');
}

template<typename T>
inline void writeln(T x) {
    write(x);
    pc('\n');
}
}

using IO::read;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;

const int maxn = 100100;

int n, m, q, B, ans[maxn], tot, ls[maxn], c[maxn];
vector<int> vq[maxn];
pii e[maxn];
bool vis[maxn], mk[maxn];

struct node {
    int i, u, v;
} a[maxn];

struct que {
    int w, p, i;
} b[maxn];

int fa[maxn], rnk[maxn], top, cnt;
pair<int *, int> stk[maxn << 1];

inline int find(int x) {
    while (x != fa[x]) {
        x = fa[x];
    }

    return x;
}

inline void merge(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) {
        return;
    }

    ++cnt;

    if (rnk[x] <= rnk[y]) {
        stk[++top] = mkp(fa + x, fa[x]);
        fa[x] = y;

        if (rnk[x] == rnk[y]) {
            stk[++top] = mkp(rnk + y, rnk[y]);
            ++rnk[y];
        }
    } else {
        stk[++top] = mkp(fa + y, fa[y]);
        fa[y] = x;
    }
}

inline void work() {
    sort(b + 1, b + q + 1, [&](const que & a, const que & b) {
        return a.p < b.p;
    });
    mems(vis, 0);
    tot = 0;

    for (int i = 1; i <= m; ++i) {
        e[++tot] = mkp(a[i].u, a[i].v);
    }

    sort(e + 1, e + tot + 1, [&](const pii & a, const pii & b) {
        return a.scd < b.scd || (a.scd == b.scd && a.fst < b.fst);
    });
    tot = unique(e + 1, e + tot + 1) - e - 1;

    for (int i = 1; i <= m; ++i) {
        a[i].i = lower_bound(e + 1, e + tot + 1, mkp(a[i].u, a[i].v), [&](const pii & a, const pii & b) {
            return a.scd < b.scd || (a.scd == b.scd && a.fst < b.fst);
        }) - e;
    }

    for (int i = 1; i <= (m + B - 1) / B; ++i) {
        vector<int>().swap(vq[i]);
    }

    for (int i = 1; i <= q; ++i) {
        vq[(b[i].w + B - 1) / B].pb(i);
    }

    for (int k = 1; k <= (m + B - 1) / B; ++k) {
        int l = (k - 1) * B + 1, r = min(k * B, m);
        top = cnt = 0;

        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
            rnk[i] = 1;
        }

        int tt = 0, j = 1;

        for (int i = l; i <= r; ++i) {
            c[++tt] = a[i].i;
            mk[a[i].i] = 1;
        }

        sort(c + 1, c + tt + 1);
        tt = unique(c + 1, c + tt + 1) - c - 1;

        for (int i : vq[k]) {
            while (j <= tot && e[j].scd <= b[i].p) {
                if (vis[j] && !mk[j]) {
                    merge(e[j].fst, e[j].scd);
                }

                ++j;
            }

            for (int j = l; j <= b[i].w; ++j) {
                vis[a[j].i] ^= 1;
            }

            int ltop = top, lcnt = cnt;

            for (int j = 1; j <= tt; ++j) {
                if (vis[c[j]] && e[c[j]].scd <= b[i].p) {
                    merge(e[c[j]].fst, e[c[j]].scd);
                }
            }

            ans[b[i].i] += cnt;

            while (top > ltop) {
                *stk[top].fst = stk[top].scd;
                --top;
            }

            cnt = lcnt;

            for (int j = l; j <= b[i].w; ++j) {
                vis[a[j].i] ^= 1;
            }
        }

        for (int i = l; i <= r; ++i) {
            vis[a[i].i] ^= 1;
            mk[a[i].i] = 0;
        }
    }
}

void solve() {
    n = read();
    m = read();
    q = read();
    B = sqrt(m);

    for (int i = 1; i <= m; ++i) {
        read();
        a[i].u = read() + 1;
        a[i].v = read() + 1;

        if (a[i].u > a[i].v) {
            swap(a[i].u, a[i].v);
        }
    }

    for (int i = 1; i <= q; ++i) {
        b[i].w = read() + 1;
        b[i].p = read() + 1;
        b[i].i = i;
    }

    work();

    for (int i = 1; i <= q; ++i) {
        b[i].p = n - b[i].p;
    }

    for (int i = 1; i <= m; ++i) {
        a[i].u = n - a[i].u + 1;
        a[i].v = n - a[i].v + 1;
        swap(a[i].u, a[i].v);
    }

    work();

    for (int i = 1; i <= q; ++i) {
        writeln(n - ans[i]);
    }
}

int main() {
    // freopen("cruising.in", "r", stdin);
    // freopen("cruising.out", "w", stdout);
    int T = 1;

    // scanf("%d", &T);
    while (T--) {
        solve();
    }

    return 0;
}