题目描述

难度分:$1777$

输入$n(2 \leq n \leq 3 \times 10^5)$表示有$n$个盒子，编号从$1$到$n$。

每个盒子都放了一个小球，其中编号为$i$的盒子放了编号为$i$的小球。

然后输入$q(1 \leq q \leq 3 \times 10^5)$和$q$个操作，格式如下：

• $1$ $x$ $y$：把编号为$y$的盒子中的小球全部放入编号为$x$的盒子中。保证$x \neq y$。

• $2$ $x$：设所有盒子中一共有$k$个小球，现在把一个新的编号为$k+1$的小球放入编号为$x$的盒子中。

• $3$ $x$：输出编号为$x$的小球所在盒子的编号。保证$x$一定在某个盒子中。

输入样例

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6

输出样例

5
4
3
1
3

算法

并查集

这个题很容易想到用并查集来做，对于并查集的$father$数组$p$，赋予$p[i]$的含义为“小球$i$在箱子$p[i]$中”。但是对于操作$1$，将$y$箱子中的小球倒入$x$箱子后，$y$箱子还可以放入新的小球，这会导致后来放入$y$的小球如果仅靠并查集来查询的话，会直接定位到$x$箱子，而这样是不对的。

可以这样来处理，将$y$中的小球倒入$x$之后，如果再来新的小球要放进$y$，就开一个新的箱子$z$ $(z \gt n)$来放，并记录$z$对应的原始箱子。

复杂度分析

时间复杂度

初始化并查集的时间复杂度为$O(n+q)$，接下来的$q$次操作，除了第$3$种操作，其他两种是$O(1)$的，第$3$种是并查集的查询操作，时间复杂度是$log$级别。因此，算法整体的时间复杂度为$O(n+q+qlogn)$。

空间复杂度

空间消耗的瓶颈由并查集决定，额外空间复杂度为$O(n+q)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 600010;
int p[N], newBox[N], originBox[N], n, q;

int find(int x) {
    return p[x] == x? x: p[x] = find(p[x]);
}

int main() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i < N; i++) {
        p[i] = i;
        newBox[i] = i;
        originBox[i] = i;
    }
    int k = n, z = n + q;
    for(int i = 1; i <= q; i++) {
        int t, x, y;
        scanf("%d%d", &t, &x);
        if(t == 1) {
            scanf("%d", &y);
            p[newBox[y]] = newBox[x];
            newBox[y] = z;
            originBox[z] = y;
            z--;
        }else if(t == 2) {
            p[++k] = newBox[x];
        }else {
            printf("%d\n", originBox[find(x)]);
        }
    }
    return 0;
}