BZOJ 1483 夢幻布丁：鏈表與啟發式合併

BZOJ 1483 夢幻布丁：鏈表與啟發式合併

題目給出一個顏色序列，支持兩種操作：

1. 查詢當前有多少個顏色塊（連續相同顏色算一塊）。
2. 將所有顏色 c1 修改為 c2。

數據範圍較大，暴力修改會超時。關鍵觀察：每次修改實際上是將一個顏色的所有位置合併到另一個顏色中。若總是將「節點數較少」的顏色合併到「節點數較多」的顏色，每個節點被移動的次數至多 O(log n)，總複雜度 O(n log n) —— 即啟發式合併。

數據結構設計

• 對每個顏色維護一個鏈表，存儲該顏色出現的所有位置（按順序）。
• src[pos] 記錄位置 pos 當前的真實顏色（考慮映射後）。
• C[col] 記錄顏色 col 當前映射到的「代表顏色」（用於處理合併方向反轉）。
• num[col] 記錄代表顏色 col 當前包含的節點數。
• now 維護當前顏色塊總數。

修改操作 Change(from, aim)

1. 找到真實代表顏色：from = C[from], aim = C[aim]。若相同直接返回。
2. 若 num[from] > num[aim]，交換兩者（確保合併小到大）。
3. 遍歷 from 的鏈表節點 pos：
   • 檢查左右鄰居：若 src[pos-1] == aim 或 src[pos+1] == aim，說明合併後會減少顏色塊，now--。
   • 將節點加入 aim 的鏈表頭部。
4. 再次遍歷更新 src[pos] = aim。
5. 釋放 from 的鏈表節點內存，清空頭指針，更新 num[aim] += num[from]，num[from] = 0。

完整代碼

#include <cstdio>
#include <cstring>
#include <iostream>
#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;
}

啟發式合併保證了 O((n+q) log n) 的時間複雜度，是解決此類顏色區間合併問題的經典技巧。