1620E - Replace the Numbers（源地址自⇔CF1620E）
目录tag
⇔构造算法、⇔数据结构、⇔并查集、⇔模拟、⇔铁牌级（*1900）
题意
给出一个空数组，规定两种操作：
- 在数组末尾加上 \(x\) ；
- 将数组中全部的 \(x\) 替换为 \(y\) 。
现在有 \(q\) 次询问，请输出结果数组。
思路
首先考虑暴力的做法，一旦遇到第二种操作，便从头遍历一遍数组。显然这会超时，但我们发现，第二种操作是无后效性的，我们考虑倒序操作数组。
倒序思考的话就很简单了：遇到第二种操作便建立（更新）一个映射，遇到第一种操作就将读入的 \(x\) 所对应的映射加入数组。这一过程就像并查集找祖先一样，但其实不然——刚刚提到，第二种操作是无后效性的，直接使用并查集的话会破坏原有的顺序，导致产生后效性。
这里其实比较绕，不太容易说清，尝试小小的总结一下：并查集是一路回溯寻找祖先；而本题由于逆序操作，映射是不断在更新的，回溯一轮即得到结果。参见下方 \(\tt{hack}\) 数据。
点击查看数据样例
4
1 2
2 6 2
2 3 1
2 2 3如本例，在读入第二组数据时，并查集搜索 \(2\) 的父亲： \(3\) 。依照无后效性原则，此时应当结束搜索，但是由于已知 \(3\) 的父亲为 \(1\) ，故并查集会将 \(2\) 链接至 \(1\) 。
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 成文