BZOJ 1483 HNOI 2009 夢幻布丁 鏈表+啟發式合並

BZOJ 1483 HNOI 2009 夢幻布丁 鏈表+啟發式合並

題目大意：給出一串顏色，有兩種操作，1.詢問有多少塊顏色。2.將一種顏色改變成另一種顏色。


思路：好像和染色什麼的比較像，但是看了題解之後發現完全不是那麼回事。
對於每一種顏色維護一個鏈表，然後在修改顏色的時候，暴力修改一種顏色成為另一種顏色，用啟發式合並可以保證復雜度不超過O(nlogn)。但是由於是啟發式合並，有可能導致你就改了反了顏色，這個時候記錄一個映射，然後把修改錯的記錄下來。各種信息仔細討論一下。。。

CODE：

#include 
#include 
#include 
#include 
#define MAX 1000010
using namespace std;
 
struct List{
    List *next;
    int pos;
     
    List(int _ = 0) {
        next = NULL;
        pos = _;
    }
}*head[MAX];
 
int cnt,asks;
int src[MAX];
int now,num[MAX];
int C[MAX];
 
void Pretreatment()
{
    for(int i = 1; i < MAX; ++i)
        C[i] = i;
}
 
inline void Add(int col,int pos)
{
    List *temp = new List(pos);
    temp->next = head[col];
    head[col] = temp;
}
 
inline void Change(int from,int aim)
{
    if(from == aim) return ;
    if(num[C[from]] > num[C[aim]])
        swap(C[from],C[aim]);
    from = C[from],aim = C[aim];
    if(head[from] == NULL)  return ;
    for(List *x = head[from]; x != NULL; x = x->next) {
        if(src[x->pos - 1] == aim)   --now;
        if(src[x->pos + 1] == aim)   --now;
        Add(aim,x->pos);
    }
    for(List *x = head[from]; x != NULL; x = x->next)
        src[x->pos] = aim;
    static List *stack[MAX];
    int top = 0;
    for(List *x = head[from]; x != NULL; x = x->next)
        stack[++top] = x;
    while(top)  delete stack[top--];
    head[from] = NULL;
    num[aim] += num[from];
    num[from] = 0;
}
 
int main()
{
    Pretreatment();
    cin >> cnt >> asks;
    int last = 0;
    for(int i = 1; i <= cnt; ++i) {
        scanf("%d",&src[i]);
        Add(src[i],i);
        ++num[src[i]];
        if(src[i] != last) {
            last = src[i];
            ++now; 
        }
    }
    for(int flag,x,y,i = 1; i <= asks; ++i) {
        scanf("%d",&flag);
        if(flag == 1) {
            scanf("%d%d",&x,&y);
            Change(x,y);
        }
        else    printf("%d\n",now);
    }
    return 0;
}