Codeforces-1620-E

题目大意

给定一个初始为空的队列，有\(n\)个操作，每种操作为以下两种中的一个: * \(1\) \(x\),往队列尾部插入一个\(x\)。 * \(2\) \(x\) \(y\),使得当前队列中所有的\(x\)都变为\(y\)。

\(1 \le n,x,y \le 5 \times 10^5\)

输出所有操作之后的队列

思路

我们不妨把队列中的数全部加进来，那么对于操作\(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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/02/15/Codeforces-1620-E/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！