【Codeforces】1620E Replace the Numbers 题解

题目大意

给定一个初始为空的队列，有 $n$ 个操作，每种操作为以下两种中的一个（$1 \le n, x, y \le 5 \times 10^5$）：

• 1 x：往队列尾部插入一个 $x$。
• 2 x y：使得当前队列中所有的 $x$ 都变为 $y$。

输出所有操作之后的队列。

思路

我们不妨把队列中的数全部加进来，那么对于操作 2，就相当于把队列中相应位置左边的所有 $x$ 变成 $y$ 对应的数，对右边没有什么影响。

且这种操作是可以叠加的，如果直接处理左边的数，时间复杂度肯定会炸。

那么我们想到，可不可以批量处理操作 2？

如果我们从右往左看的话，操作 2 是可以直接叠加的：2 x y 之后，我们添加 $x$ 时，就直接把它替换为 $y$ 对应的数（因为 $y$ 可能已经被替换过了）。

每次只对某位置前的数进行操作，可以考虑这种反向的做法。

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int maxN = 5e5 + 7;
int n, t[maxN], x[maxN], y[maxN], p[maxN];
vector<int> ans;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &t[i], &x[i]);
        if(t[i] == 2)
            scanf("%d", &y[i]);
    }
    for(int i = 1; i <= maxN - 1; ++i) 
        p[i] = i;
    for(int i = n; i >= 1; --i) {
        if(t[i] == 1)
            ans.push_back(p[x[i]]);
        else
            p[x[i]] = p[y[i]];
    }
    for(int i = ans.size() - 1; i >= 0; --i)
        printf("%d ", ans[i]);
    return 0;
}