注意，本文复杂度分析时，为了方便，假设 (n) 与 (m) 同阶。
首先写几个数据手玩一下，发现答案貌似和每个塔中“编号相邻的圆盘”的对数有关。（若 (i) 和 (i+1) 在同一个塔中，则它们为一对“编号相邻的圆盘”，简称“相邻对”）
具体来说，设所有塔中“相邻对”的数量和为 (sum) ，则答案为 (n - sum - 1)。
比如([1,2,6][3,4][5])
可以这样：([1,2,6][3,4][5] ightarrow [6][1,2,3,4][5] ightarrow [6][][1,2,3,4,5] ightarrow [1,2,3,4,5,6][][])
有 ((1,2) (3,4)) 这两对，故答案为 (6 - 2 - 1 = 3)。
现在问题就是维护这个 (sum) 了。
直接合并显然会变成 (O(n^2))。可以考虑类似于启发式合并的东西？
自然想到了并查集，维护所有圆盘。合并两个（圆盘）集合时，两集合原本就有的“相邻对”显然不会被破坏，(sum) 显然不会减少。增加的部分，肯定是两个集合拼起来时创出来的。例如 ([1,3,7][2,4,5] ightarrow [1,2,3,4,5,7]) 中的 ((2,3))、((3,4))。
设当前合并的集合分别为 (S_1) , (S_2)。
对于 (S_1)，设它的元素有 ({x_1,x_2,...,x_k}) ， 考虑 (x_1 - 1,x_1 + 1,x_2 - 1,x_2 + 1, ... ,x_k - 1,x_k + 1) 这些数中的每个数 (u)，若 (S_2) 里也有 (u)，(sum) 便增加 (1)（容易发现，(u) 出现便会与 (S_1) 的某个数拼成“相邻对”，如((x_1,x_1 - 1))，无需去重）。"(S_2) 里是否有 (u)" 可以通过并查集的 (find) 实现。
令 (siz_{S_1} < siz_{S_2}) ，再加个路径压缩，通过启发式合并的知识，可以知道 (find) 的次数不超过 (nlogn)，且 (find) 复杂度平均为 (O(alpha (n)))，复杂度就不会超过 (O(n logn alpha (n)))。实际上，由于并查集的 (find) 函数有时只要 (O(1)) 时间，可能跑不满这个上界。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,ll>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=1000000007;
const double pi=3.1415926535897932,eps=1e-6;
void chmax(pii &x,pii y){if(x < y) x = y;}
void chmin(int &x,int y){if(x > y) x = y;}
int n,m,C[200005],v[200005],sumv,siz[200005];
int fa[200005],pos[200005];
vector<int> ve[200005];
int find(int x){
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void unite(int x,int y){
int xx = find(x), yy = find(y);
if(siz[xx] > siz[yy]) swap(xx,yy);
//xx is under yy
v[yy] += v[xx]; //其实 v 这个数组可以不用
siz[yy] += siz[xx];
rap(i,0,siz[xx]) {
int u = ve[xx][i];
if(u > 1 && find(u - 1) == yy) v[yy] ++, sumv++;
if(u < n && find(u + 1) == yy) v[yy] ++, sumv++;
}
while(ve[xx].size()) ve[yy].pb(ve[xx].back()),ve[xx].pop_back();
fa[xx] = fa[yy];siz[xx] = 0;
}
int main()
{
scanf("%d%d",&n,&m);
rep(i,1,n) fa[i] = i, ve[i].pb(i), siz[i] = 1;
rep(i,1,n) {
scanf("%d",C+i);
if(pos[C[i]]) unite(pos[C[i]], i);
pos[C[i]] = i;
}
printf("%d
",n - sumv - 1);
rap(i,1,m) {
int x,y;
scanf("%d%d",&x,&y);
unite(pos[x],pos[y]);
printf("%d
",n - sumv - 1);
}
return 0;
}