【题解】AGC 002D Stamp Rally

Problem

传送门 ＞ω＜

题目大意
在无向图上给定一些点对，问从这些每一个点对出发遍历 $v_i$ 个顶点所经过的最小编号的边为多少

Solution

考虑从小到大加边，发现在当前边权下能经过的顶点数为联通块大小
时间复杂度 $q * m$
显然是不可接受的

所以可以想办法先把图弄出来再询问询问在某个时刻是否成立
可持久化并查集 + 二分
考虑下是否能查询在某个时刻的 num ？
可以，一路查询上去的话，最后的 num 是可以存下来的，解决

但是时间复杂度 $q \log^2 n\log m$
很虚啊有没有

或者整体二分 + 并查集？
每次暴力重构
但是暴力重构貌似和总长度有关...
所以考虑暴力撤销并查集，每次回到父亲节点的状态，然后重新加边

时间复杂度 $n\log^2$
终于能过啦！！！

代码

整体二分略丑 qwq

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
#define mid ((l + r) >> 1)

struct OPT {
    int u , v;
    int z;
    int id;
}e[N * 2] , E[2][N * 2];
int n , m , q;
int fa[N];
int num[N];
void init() {
    n = read(); m = read();
    for(int i = 1 ; i <= m ; ++ i) {
        e[i].u = read();
        e[i].v = read();
        e[i].id = i;
        e[i].z = 0;
    }
    q = read();
    for(int i = 1 ; i <= q ; ++ i) {
        e[i + m].u = read();
        e[i + m].v = read();
        e[i + m].id = i;
        e[i + m].z = read();
    }
}

int find(int x) {
    while(x != fa[x]) x = fa[x];
    return x;
}
int ans[N];
int sta[N] , top;
void work(int l , int r , int ll , int rr) {
    int begintop = top;
    int tot0 = 0 , tot1 = 0;
    if(ll > rr) return;
    if(l == r) {
        for(int i = ll ; i <= rr ; ++ i)
            if(e[i].z)
                ans[e[i].id] = l;
        return;
    }
    tot0 = tot1 = 0;
    for(int i = ll ; i <= rr ; ++ i)
        if(!e[i].z && e[i].id <= mid) {
            int x = find(e[i].u) , y = find(e[i].v);
            if(x != y) {
                if(num[x] > num[y]) swap(x , y);
                fa[x] = y; num[y] += num[x];
                sta[++ top] = x;
            }
            E[0][++ tot0] = e[i];
        }
        else if(!e[i].z) E[1][++ tot1] = e[i];
    for(int i = ll ; i <= rr ; ++ i) {
        if(e[i].z) {
            int u = find(e[i].u);
            int v = find(e[i].v);
            if(u == v) {
                if(num[u] >= e[i].z) E[0][++ tot0] = e[i];
                else E[1][++ tot1] = e[i];
            }
            else {
                if(num[u] + num[v] >= e[i].z) E[0][++ tot0] = e[i];
                else E[1][++ tot1] = e[i];
            }
        }
    }
    for(int i = 1 ; i <= tot0 ; ++ i)
        e[ll + i - 1] = E[0][i];
    for(int i = 1 ; i <= tot1 ; ++ i)
        e[ll + tot0 + i - 1] = E[1][i];
    
    work(mid + 1 , r , ll + tot0 , rr);
    while(top > begintop) {
        num[fa[sta[top]]] -= num[sta[top]];
        fa[sta[top]] = sta[top];
        -- top;
    }
    work(l , mid , ll , ll + tot0 - 1);
    return;
}
int main() {
    init();
    for(int i = 1 ; i <= n ; ++ i) {fa[i] = i; num[i] = 1;}
    work(1 , m , 1 , m + q);
    for(int i = 1 ; i <= q ; ++ i)
        printf("%d\n" , ans[i]);
    return 0;
}