Description
给定一个长度为 (n) 的序列 ，一共有 (m) 个操作。
每次操作的内容为：给定 (x, y)，序列中所有 (x) 会变成 (y)。
同时我们有一份代码：
int ans = 2147483647;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[i] == a[j])
ans = std::min(ans, j - i);
}
}
std::cout << ans << std::endl;
请在每次修改后输出代码运行的结果。
Hint
(1le n,mle 10^5)
Soluiton
很明显题中所给的代码的意义是，求所有相等元素的间隔距离的最小值。
又注意到，操作进行下去时，颜色种类数不会增加，那么 ans 的值也只能减少。
先离线下来，离散化一下，然后考虑平衡树启发式合并。
我们开 总颜色种类数 个 set。pos[i] 表示颜色 (i) 在序列中的位置的集合。
当有操作 x y 时， 就把 pos[x] 的所有元素“倾倒”到 pos[y] 中，同时更新答案。
但这样显然会被卡，直接交上去剩几分看RP。
于是乎有了 启发式合并。并不是什么深奥的科技，就是在原算法的基础上，限制只能从小集合“倾倒”到大集合中去。显然比反过来倒要快。注意交换的话，要标记一下（Code 中的 refer）。
启发式合并如何保证复杂度？假设一个元素 (i) 在某个集合中，那么一次次的合并之后（为了方便解释，先假定 (i) 的所在集合总是上述的“小集合”），(i) 的所在集合至少会扩大两倍。但是我们发现这里总共也就 (n) 个元素，于是每个元素被最多合并 (log n) 次。算上平衡树复杂度，就是 (O(nlog^2 n))。
虽说两个 (log)，但常数不大，而且本来就能过。
Code
注：std::set 的 insert 函数的返回值是一个 pair，取其 first 可以直接得到插入元素的迭代器。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : LOJ #516 「LibreOJ β Round #2」DP 一般看规律
*/
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef set<int>::iterator setIt;
const int N = 1e5 + 5;
int n, q, ary[N];
int qry[2][N];
int ans = 2147483647;
int refer[N << 2];
set<int> pos[N << 2];
int val[N << 2];
int cnt = 0;
void merge(int x, int y) {
if (x == y) return;
if (pos[refer[x]].size() > pos[refer[y]].size())
swap(refer[x], refer[y]);
x = refer[x], y = refer[y];
/*x -> y*/
for (setIt itx = pos[x].begin(); itx != pos[x].end(); itx++) {
setIt ity = pos[y].insert(*itx).first;
if (++ity != pos[y].end()) ans = min(ans, *ity - *itx);
if (--ity != pos[y].begin()) ans = min(ans, *itx - *(--ity));
}
pos[x].clear();
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> q;
for (register int i = 1; i <= n; i++)
cin >> ary[i], val[++cnt] = ary[i];
for (register int i = 1; i <= q; i++) {
cin >> qry[0][i] >> qry[1][i];
val[++cnt] = qry[0][i], val[++cnt] = qry[1][i];
}
sort(val + 1, val + 1 + cnt), cnt = unique(val + 1, val + 1 + cnt) - val - 1;
for (register int i = 1; i <= n; i++)
ary[i] = lower_bound(val + 1, val + 1 + cnt, ary[i]) - val;
for (register int i = 1; i <= q; i++) {
qry[0][i] = lower_bound(val + 1, val + 1 + cnt, qry[0][i]) - val;
qry[1][i] = lower_bound(val + 1, val + 1 + cnt, qry[1][i]) - val;
}
for (register int i = 1; i <= cnt; i++)
refer[i] = i;
for (register int i = 1; i <= n; i++) {
setIt it = pos[ary[i]].insert(i).first;
if (++it != pos[ary[i]].end()) ans = min(ans, *it - i);
if (--it != pos[ary[i]].begin()) ans = min(ans, i - *(--it));
}
for (register int i = 1; i <= q; i++) {
merge(qry[0][i], qry[1][i]);
cout << ans << '
';
}
}