题解：

神奇的一道题，首先我们考虑如果我们一个个的搬这个碟子的话答案是n-1，但是如果我们有两个相邻的碟子是临近的那么就可以把他们看成一个整体这样的话答案就可以减去1了。我们按照每堆的top点建立树，每次合并的时候，对于小树的每个节点我们都判断它在原数组的相邻节点的祖先节点是不是合并的大树top点，如果是的既然相邻那么他们的半径就是差值最小的，也就是说可以把他们看成一个整体了答案就可以减去1了，然后再改变小树的祖先节点和原数组中记录的top节点改变就行了。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef long double ld;
const int N=2e5+10;
int pos[N],pre[N];
vector<int> g[N];
int find(int x)
{
    if(x==pre[x]) return pre[x];
    return pre[x]=find(pre[x]);
}
signed main()
{
    int n,m; scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) {
        scanf("%d",&pos[i]); pos[i]--;
        g[pos[i]].push_back(i);
    }
    int res=n-1;
    for(int i=0;i<m;i++) pre[i]=i;
    for(int i=1;i<n;i++) {
        if(pos[i-1]==pos[i]) res--;
    }
    printf("%d\n",res);
    for(int i=0;i<m-1;i++){
        int a,b; scanf("%d%d",&a,&b); a--,b--;
        int u=find(a),v=find(b);
        if((int)g[u].size()>(int) g[v].size()) swap(u,v);
        for(auto it:g[u]){
            if(it+1<n&&pos[it+1]==v) res--;
            if(it-1>=0&&pos[it-1]==v) res--;
            g[v].push_back(it);
        }
        for(auto it:g[u]) pos[it]=v;
//        g[u].clear();
        pre[u]=v;
        printf("%d\n",res);
    }
}

本文地址：https://blog.csdn.net/weixin_42979819/article/details/107336574