牛客练习赛70 D 数树

没看到题目中条件保证是一颗森林，自行加强题目。
这里采用时间线段树+回退并查集来解决。
并查集可以O(1)的插入，很难O(1)的支持删除操作，但是可以回退。
我们使用时间线段树，将所有操作锁定为插入操作，使用回退并查集维护即可。
复杂度O(nlogn)。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

#define lson rt * 2
#define rson rt * 2 + 1
#define MP make_pair

const int N = 2e5 + 100;

int n, tp, tt;
int op[N], uu[N], vv[N], id[N], has[N], ans[N];
pair<int, int> mp[N];
int tim[N];

struct node {
    int op, u, v;
    node() {}
    node(int op, int u, int v) :op(op), u(u), v(v) {}
};

vector<node> V[N * 4], G[N * 4];

void insert(int rl, int rr, node x, int l, int r, int rt) {
    if (rl == l && rr == r) {
        V[rt].push_back(x);
        return;
    }
    int m = (l + r) / 2;
    if (rr <= m) insert(rl, rr, x, l, m, lson);
    else if (m < rl) insert(rl, rr, x, m + 1, r, rson);
    else {
        insert(rl, m, x, l, m, lson);
        insert(m + 1, rr, x, m + 1, r, rson);
    }
}

int fa[N], sz[N], sum;

void change(int op, int id, int x, vector<node> &V) {
    if (op == 1) {
        V.push_back(node(op, id, fa[id]));
        fa[id] = x;
    }
    if (op == 2) {
        V.push_back(node(op, id, sz[id]));
        sz[id] = x;
    }
    if (op == 3) {
        V.push_back(node(op, 0, sum));
        sum = x;
    }
}

void recover(node x) {
    if (x.op == 1) {
        fa[x.u] = x.v;
    }
    if (x.op == 2) {
        sz[x.u] = x.v;
    }
    if (x.op == 3) {
        sum = x.v;
    }
}

int find(int x, vector<node> &V) {
    if (x == fa[x]) return x;
    int f = find(fa[x], V);
    change(1, x, f, V);
    return f;
}

void join(int u, int v, vector<node> &V) {
    u = find(u, V);
    v = find(v, V);
    if (u == v) return;
    if (sz[u] == 1 && sz[v] == 1) change(3, 0, sum + 1, V);
    if (sz[u] > 1 && sz[v] > 1) change(3, 0, sum - 1, V);
    change(1, u, v, V);
    change(2, v, sz[u] + sz[v], V);
}

void query(int l, int r, int rt) {
    for (node x : V[rt]) {
        if (x.op == 1) {
            join(x.u, x.v, G[rt]);
        }
    }
    if (l == r) {
        for (node x : V[rt]) {
            if (x.op == 3) {
                ans[l] = sum;
            }
        }
    }
    else {
        int m = (l + r) / 2;
        query(l, m, lson);
        query(m + 1, r, rson);
    }
    for (int i = G[rt].size() - 1; i >= 0; i--) {
        recover(G[rt][i]);
    }
    G[rt].clear();
    V[rt].clear();
    vector<node> v, g;
    swap(G[rt], g);
    swap(V[rt], v);
}

int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", op + i);
        if (op[i] != 3) {
            scanf("%d%d", uu + i, vv + i);
            has[++tp] = uu[i];
            has[++tp] = vv[i];
        }
    }
    sort(has + 1, has + tp + 1);
    tp = unique(has + 1, has + tp + 1) - has;
    for (int i = 1; i <= n; i++) {
        if (op[i] != 3) {
            uu[i] = lower_bound(has + 1, has + tp, uu[i]) - has;
            vv[i] = lower_bound(has + 1, has + tp, vv[i]) - has;
            if (uu[i] > vv[i]) swap(uu[i], vv[i]);
            mp[++tt] = MP(uu[i], vv[i]);
        }
    }
    sort(mp + 1, mp + tt + 1);
    tt = unique(mp + 1, mp + tt + 1) - mp;
    for (int i = 1; i <= n; i++) {
        if (op[i] == 3) continue;
        int id = lower_bound(mp + 1, mp + tt, MP(uu[i], vv[i])) - mp;
        if (op[i] == 1) {
            if (tim[id] == 0) {
                tim[id] = i;
            }
        }
        else {
            if (tim[id] != 0) {
                insert(tim[id], i, node(1, uu[i], vv[i]), 1, n, 1);
            }
            tim[id] = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (op[i] == 3) {
            insert(i, i, node(3, 0, 0), 1, n, 1);
        }
        else if (op[i] == 1) {
            int id = lower_bound(mp + 1, mp + tt, MP(uu[i], vv[i])) - mp;
            if (tim[id] == i) {
                insert(i, n, node(1, uu[i], vv[i]), 1, n, 1);
            }
        }
    }
    for (int i = 1; i <= tp; i++) fa[i] = i, sz[i] = 1;
    query(1, n, 1);
    for (int i = 1; i <= n; i++)
        if (op[i] == 3)
            printf("%d\n", ans[i]);
    return 0;
}