AT1998 [AGC002D] Stamp Rally

https://www.luogu.com.cn/problem/AT1998

整体二分板子题

考虑二分编号，然后用并查集维护大小，注意并查集要支持撤回，用按秩合并并查集即可

时间复杂度$O(nlo{g}^{2}n)$

可以把dfs换成bfs，即把二分的建成一棵树，一层层处理，这样并查集就不用支持可撤回了，时间复杂度降到$O(nlogn)$

只写了第一种，第二种后面再补
code:

#include<bits/stdc++.h>
#define N 200050
using namespace std;
int fa[N], siz[N], top, ans[N];
pair<int, int> sta[N];
struct Q {
    int x, y, z, id;
} q[N], a[N], b[N];
struct E {
    int u, v;
} e[N];
int get(int x) {
    return fa[x] == x? x : get(fa[x]);
}
void merge(int x, int y) {
    x = get(x), y = get(y);
    if(x == y) return;
    if(siz[x] > siz[y]) swap(x, y);
    sta[++ top] = make_pair(x, y);
    fa[x] = y, siz[y] += siz[x];
}
void solve(int l, int r, int L, int R) { 
    // printf("%d %d %d %d\n", l, r, L, R);
    // for(int i = L; i <= R; i ++) printf(" %d ", q[i].id); printf("\n");
    if(l == r) {
        for(int i = L; i <= R; i ++) ans[q[i].id] = l;
        int x = get(e[l].u), y = get(e[l].v);
        if(x == y) return ;
        if(siz[x] > siz[y]) swap(x, y);
        fa[x] = y, siz[y] += siz[x];
        return ;
    }
    int mid = (l + r) >> 1;
    for(int i = l; i <= mid; i ++) merge(e[i].u, e[i].v);
    int gs = 0, gss = 0;
    for(int i = L; i <= R; i ++) {
        int x = get(q[i].x), y = get(q[i].y), s = 0;
        if(x == y) s = siz[x];
        else s = siz[x] + siz[y];
        if(s >= q[i].z) a[++ gs] = q[i];
        else b[++ gss] = q[i];
    }
    while(top) {
        int x = sta[top].first, y = sta[top].second; top --;
        fa[x] = x; siz[y] -= siz[x];
    }
    for(int i = 1; i <= gs; i ++) q[L + i - 1] = a[i];
    for(int i = 1; i <= gss; i ++) q[L + gs + i - 1] = b[i];
    solve(l, mid, L, L + gs - 1), solve(mid + 1, r, L + gs, R);
}
int n, m, qq;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) fa[i] = i, siz[i] = 1;
    for(int i = 1; i <= m; i ++) scanf("%d%d", &e[i].u, &e[i].v);
    scanf("%d", &qq);
    for(int i = 1; i <= qq; i ++) scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z), q[i].id = i;
    solve(1, m, 1, qq);
    for(int i = 1; i <= qq; i ++) printf("%d\n", ans[i]);
    return 0;
}