Replace the Numbers

Replace the Numbers(VOJ)

Replace the Numbers(codeforces)

题目大意

有一个空序列和$q$次操作，操作分如下两类：

• $1,x$，意为在数列末尾加一个数字
• $2,x,y$，意为将当前数列中的所有值为$x$的数替换为$y$

求出$q$次操作后的序列。

题解

我们可以倒着做，从最后一个开始。设$f_x$表示此时的$x$在最后是什么值。从后往前遍历每次询问，对于操作1，将答案中这个位置的值赋为$f_x$；对于操作2，令$f_x=f_y$，也就是说在下一次对$x$修改之前，$x$的实际值等于$y$的实际值。大家可以自己举几个例子来理解。

code

#include
using namespace std;
int n,fa[500005],ans[500005];
struct node{
	int tp,x,y;
}w[500005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=500000;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i].tp);
		if(w[i].tp==1) scanf("%d",&w[i].x);
		else scanf("%d%d",&w[i].x,&w[i].y);
	}
	for(int i=n;i>=1;i--){
		if(w[i].tp==2){
			fa[w[i].x]=fa[w[i].y];
		}
		else{
			ans[++ans[0]]=fa[w[i].x];
		}
	}
	for(int i=ans[0];i;i--) printf("%d ",ans[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28