BZOJ1483:[HNOI2009]梦幻布丁 链表启发式合并

思路:

保存所有颜色组成的链表,改颜色时就把两个链表合并,合并方式利用归并排序即可.

易知链表的数目只会越来越少,因此我们进行启发式合并,每一次将小的链表合并到大的链表里面.

这样最坏情况下只需合并\(O(logn)\)次,每一次合并复杂度为\(O(n)\),因此总的时间复杂度为\(O(nlogn)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 100010
struct Node{
    Node*nxt;
    int ins;
    Node(){}
    Node(int _ins):ins(_ins){}
}*null;
Node*begin[N],*end[N];int c[N],siz[N];
 
map<int,int>M;int id;
 
int Ask(int x){return M[x];}
 
int res;
inline void Merge(int x,int y,int to){//Merge color y to color x
    static Node*stk1[N],*stk2[N];
    int id1=0,id2=0;
    int labx=M[x],laby=M[y],lastans=0,nowans=0;
    for(Node*p=begin[labx];p!=null;p=p->nxt)stk1[++id1]=p,lastans+=p->nxt->ins-p->ins>1;
    for(Node*p=begin[laby];p!=null;p=p->nxt)stk2[++id2]=p,lastans+=p->nxt->ins-p->ins>1;
    int i=1,j=1;
    Node*last=new Node(0),*S=last;
    for(;i<=id1&&j<=id2;last=last->nxt)
        if(stk1[i]->ins<stk2[j]->ins)last->nxt=stk1[i++];else last->nxt=stk2[j++];
    while(i<=id1)last->nxt=stk1[i++],last=last->nxt;
    while(j<=id2)last->nxt=stk2[j++],last=last->nxt;
    last->nxt=null;
    for(Node*p=S->nxt;p!=null;p=p->nxt)nowans+=p->nxt->ins-p->ins>1;
    begin[labx]=S->nxt;
    siz[labx]+=siz[laby];
    int t=M[x];M[x]=M[y]=0,M[to]=t;
    res=res-lastans+nowans;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int n,m;scanf("%d%d",&n,&m);
    register int i,j;int x;
 
    null=new Node(INF);
 
    int now;
    for(i=1;i<=n;++i){
        scanf("%d",&x);
        if(!M[x])M[x]=++id;++siz[now=M[x]];
        Node*p=new Node(i);
        if(end[now])end[now]->nxt=p,end[now]=p;
        else begin[now]=end[now]=p;
    }
    for(i=1;i<=id;++i)end[i]->nxt=null;
 
    for(i=1;i<=id;++i)
        for(Node*p=begin[i];p!=null;p=p->nxt)res+=p->nxt->ins-p->ins>1;
 
    int qte,a,b;
    while(m--){
        scanf("%d",&qte);
        if(qte==1){
            scanf("%d%d",&a,&b);
            if(a==b)continue;
            if(M[a]==0)continue;
            if(!M[b]){M[b]=M[a],M[a]=0;continue;}
            if(siz[M[a]]>siz[M[b]])Merge(a,b,b);else Merge(b,a,b);
        }
        else printf("%d\n",res);
    }
    return 0;
}