BZOJ 2243 [SDOI2011] 染色：樹鏈剖分與線段樹區間合並維護顏色段數

問題描述

給定 n 個節點的無根樹，初始各節點有顏色。支援兩種操作（m ≤ 1e5）：
1. C a b c：將節點 a 到 b 路徑上所有點染成顏色 c。
2. Q a b：詢問路徑 a-b 上顏色段數（連續相同顏色算一段，如 "112221" 有 3 段）。

解題思路

1. 樹鏈剖分（Heavy-Light Decomposition）

將樹分解為若干重鏈，每條重鏈在線段樹上對應一個連續區間。路徑操作轉化為 O(log n) 個區間操作。

2. 線段樹節點資訊

每個節點維護：
- num：區間內顏色段數
- l：左端點顏色
- r：右端點顏色
- lazy：區間染色標記（-1 表示無）

3. 區間合併邏輯

void push_up(int id) {
    t[id].l = t[lson].l;
    t[id].r = t[rson].r;
    t[id].num = t[lson].num + t[rson].num;
    if (t[lson].r == t[rson].l) t[id].num--; // 邊界顏色相同，段數 -1
}

4. 查詢路徑段數

將路徑拆解為若干區間，依序查詢並合併結果。注意合併時需檢查相鄰區間邊界顏色是否相同，避免重複計數。

關鍵程式碼結構

struct Node { int l, r, num, lazy; } t[800005];

void add(int id, int L, int R, int l, int r, int v) { // 區間染色
    if (l <= L && R <= r) { t[id].l = t[id].r = v; t[id].num = 1; t[id].lazy = v; return; }
    push_down(id);
    int mid = (L+R)>>1;
    if (l <= mid) add(lson, L, mid, l, r, v);
    if (r > mid) add(rson, mid+1, R, l, r, v);
    push_up(id);
}

void query(int id, int L, int R, int l, int r, int ttt) { // 區間查詢
    if (l <= L && R <= r) { if (ttt != 2) ans += t[id].num; if (L == R) xx = t[id].l; return; }
    push_down(id);
    int mid = (L+R)>>1;
    if (r <= mid) query(lson, L, mid, l, r, ttt);
    else if (l > mid) query(rson, mid+1, R, l, r, ttt);
    else {
        if (t[lson].r == t[rson].l) ans--;
        query(lson, L, mid, l, r, ttt);
        query(rson, mid+1, R, l, r, ttt);
    }
}

複雜度分析

預處理 DFS O(n)，每次操作 O(log² n)（重鏈剖分 log n 段 × 線段樹 log n），總複雜度 O((n+m) log² n)，空間 O(n)，滿足限制。

注意事項

• 顏色可為 0，lazy 初始值設 -1 或顏色 +1 避免衝突。
• 查詢合併順序影響邊界判斷，需嚴格按路徑順序處理。