题解：AT_abc279_f BOX

VitrelosTia · 2025-01-16 07:50:43 · 题解

操作 2，3 是简单的，问题在操作 1 暴力是 O(n) 的。但这是个合并操作，那自然想到启发式合并。但是合并是有方向的，你的启发式合并必须是小的合到大的上，考虑维护：

最后询问的答案是 rnk_{pos_x}。

对于操作 1，直接把 siz 小的合并到大的上，要修改 vector 和 pos，如果 siz_x > siz_y，还要交换 o 来改变 x，y 实际表示的位置，然后为了记录答案，还要把 rnk 给交换一下。

对于操作 2，直接加入就行了。代码实现比较简单。

const int N = 1e6 + 5;
int n, Q, pos[N], o[N], rnk[N]; vector <int> v[N];

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> Q; int k = n;
    for (int i = 1; i <= n; i++) v[i].push_back(i), pos[i] = i, o[i] = i, rnk[i] = i;
    for (int op, x, y; Q--; ) {
        cin >> op >> x;
        if (op == 1) {
            cin >> y;
            if (v[o[x]].size() < v[o[y]].size()) {
                for (int t : v[o[x]]) v[o[y]].push_back(t), pos[t] = o[y];
                v[o[x]].clear(); swap(o[x], o[y]); swap(rnk[o[x]], rnk[o[y]]);
            }
            else {
                for (int t : v[o[y]]) v[o[x]].push_back(t), pos[t] = o[x];
                v[o[y]].clear();
            }
        }
        if (op == 2) k++, v[o[x]].push_back(k), pos[k] = o[x];
        if (op == 3) cout << rnk[pos[x]] << '\n';
    }
    return 0;
}