1620E - Replace the Numbers（源地址自⇔CF1620E）

• 1620E - Replace the Numbers（源地址自⇔CF1620E）
  • tag
  • 题意
  • 思路
  • AC代码
  • 错误次数

tag

⇔构造算法、⇔数据结构、⇔并查集、⇔模拟、⇔铁牌级（*1900）

题意

给出一个空数组，规定两种操作：

• 在数组末尾加上 \(x\) ；
• 将数组中全部的 \(x\) 替换为 \(y\) 。

现在有 \(q\) 次询问，请输出结果数组。

思路

首先考虑暴力的做法，一旦遇到第二种操作，便从头遍历一遍数组。显然这会超时，但我们发现，第二种操作是无后效性的，我们考虑倒序操作数组。

倒序思考的话就很简单了：遇到第二种操作便建立（更新）一个映射，遇到第一种操作就将读入的 \(x\) 所对应的映射加入数组。这一过程就像并查集找祖先一样，但其实不然——刚刚提到，第二种操作是无后效性的，直接使用并查集的话会破坏原有的顺序，导致产生后效性。

这里其实比较绕，不太容易说清，尝试小小的总结一下：并查集是一路回溯寻找祖先；而本题由于逆序操作，映射是不断在更新的，回溯一轮即得到结果。参见下方 \(\tt{hack}\) 数据。

AC代码

//====================
LL n, ans, num, fa[MAX], x[MAX], y[MAX], k[MAX];
bool Ans;
vector<int> v;
//====================
void Clear() {
	ans = 0; Ans = true;
}
void Solve() {
	cin >> n;
	FOR(i, 1, n) {
		cin >> k[i] >> x[i];
		if(k[i] == 2) cin >> y[i];
	}
	FOR(i, 1, MAX - 2) fa[i] = i;
	
	FORD(i, 1, n) {
		if(k[i] == 2) fa[x[i]] = fa[y[i]];
		else v.push_back(fa[x[i]]);
	}
	reverse(v.begin(), v.end());
	for(auto it : v) cout << it << " ";
}

错误次数

文 / WIDA
2022.01.18 成文
首发于WIDA个人博客，仅供学习讨论

更新日记：
2022.01.18 成文