做了很久了吧，但现在才写题解……（斜眼

首先记录一个起始的颜色段数，然后每种颜色都要用链表顺序记下该颜色有哪些点。然后合并的时候合并两个链表——最优策略显然是启发式合并。

但是，很多时候并不是把小链表的扔到大的里面的情况，而是恰好反过来的情况，如何处理？

这种时候，我们可以交换两个颜色的“真实身份”。合并的时候，把每个点当成它的“真实身份”处理即可。

代码：

/**************************************************************
    Problem: 1483
    User: danihao123
    Language: C++
    Result: Accepted
    Time:444 ms
    Memory:20352 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using std::swap;
const int maxn=1000005;
int fact[maxn];
int first[maxn],next[maxn];
int siz[maxn];
 
int color[maxn];
int cnt=0;
int main(){
  register int i,j,last,ans=0;
  int n,m,op,a,b;
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++){
    scanf("%d",&color[i]);
    cnt++;
    next[cnt]=first[color[i]];
    first[color[i]]=cnt;
    fact[color[i]]=color[i];
    siz[color[i]]++;
    if(color[i]!=color[i-1]){
      ans++;
    }
  }
  while(m--){
    scanf("%d",&op);
    if(op==2){
      printf("%d\n",ans);
    }else{
      scanf("%d%d",&a,&b);
      if(a==b){
        continue;
      }
      if(siz[fact[a]]>siz[fact[b]]){
        swap(fact[a],fact[b]);
      }
      a=fact[a];b=fact[b];
      if(siz[a]==0){
        continue;
      }
      for(j=first[a];j;j=next[j]){
        if(color[j-1]==b) ans--;
        if(color[j+1]==b) ans--;
      }
      for(j=first[a];j;j=next[j]){
        color[j]=b;
        last=j;
      }
      next[last]=first[b];
      first[b]=first[a];
      siz[b]+=siz[a];
      siz[a]=0;
      first[a]=0;
    }
  }
  return 0;
}

• 相关文章
• 全局相关文章