Farm Updates (USACO Gold 2022 January)

关键条件是加边只在active的farm间，所以这里的加边操作不会改变任何farm是否relevant，所以可以倒过来处理。使用union-find，只有R、D事件影响relevancy，R操作将连通分量合并，D操作可能将所在连通分量全部变成relevant的。

具体实现细节比较多：

没有disable的节点要记得处理
没有remove的边要记得处理
并查集需要保存连通分量里的节点列表（这里保存了非relevant的节点列表inact[]，保存全部节点列表也行），但合并时需要把小的连通分量合并到大的，否则节点列表复制会导致10以后case TLE.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
// n <= 1e5, Q <= 2e5
int n, Q;
int ans[100005];
struct E {
    char t;       // D, A, R
    int i,j;      // (i,j) for add edge, i for R or D
};
E es[200005];
vector<E> edges;
bool a[100005];     // active vertex
vector<bool> e0;    // edges that are not removed over the whole course
int fa[100005];
vector<int> inact[100005];      // inactive vertices for each component
 
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
 
void add_edge(int x, int q) {
    int u = find(edges[x].i), v = find(edges[x].j);   // merge u and v
    if (u == v) return;
    if (!a[u] && a[v] || a[u] && !a[v]) {    // one active
        fa[u] = v;
        if (!a[u]) swap(u,v);   // u active, v inactive
        for (int i: inact[v]) {
            // printf("linking %d and %d: setting [%d] to %d\n", u, v, i, q-1);
            ans[i] = q-1;
        }
        a[v] = true;
        inact[v].clear();
    } else {
        if (!a[u] && !a[v]) {
            if (inact[u].size() > inact[v].size()) swap(u,v);   // add smaller to larger
            for (int p: inact[u]) inact[v].push_back(p);
            inact[u].clear();
        }
        fa[u] = v;
    }
}
 
int main() {
    scanf("%d %d", &n, &Q);
    fill(a, a+n+1, true);
    edges.push_back({'A',0,0});     // make edges 1-based
    e0.push_back(true);
    for (int i = 1; i <= Q; i++) {
        char s[10];
        scanf("%s %d", s, &es[i].i);            // event list
        es[i].t = s[0];
        if (s[0] == 'A') {
            scanf("%d", &es[i].j);              
            edges.push_back(es[i]);             // build edge list
            e0.push_back(true);
        }
        if (s[0] == 'D') a[es[i].i] = false;    // build initial active list
        if (s[0] == 'R') e0[es[i].i] = false;
    }
 
    // execute events backwards and apply union-find
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        if (a[i]) ans[i] = Q;           // add all initial vertices
        else inact[i].push_back(i);     
    }
    for (int i = 1; i < e0.size(); i++)
        if (e0[i]) add_edge(i, Q+1);    // add all initial edges
    for (int q = Q; q >= 1; q--) {
        E e = es[q];
        if (e.t == 'D') {
            // activate all vertices in component
            int u = find(e.i);
            if (!a[u]) {
                a[u] = true;
                for (int i: inact[u]) ans[i] = q-1;
                inact[u].clear();
            }
        } else if (e.t == 'R') {
            add_edge(e.i, q);
        }
    }
 
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
 
    return 0;
}