HDU 1698 Just a Hook：線段樹區間賦值與區間求和經典應用

HDU 1698 Just a Hook：線段樹區間賦值與區間求和經典應用

題目來源：2008 "Sunline Cup" National Invitational Contest
核心標籤：線段樹、區間賦值、懶標記思想、區間求和

題目大意

鉤子由 N 根連續小棍組成（N ≤ 100,000），初始全為銅（值 1）。Q 次操作（Q ≤ 100,000），每次將區間 [X, Y] 變為某種金屬：銅(1)、銀(2)、金(3)。最後求鉤子總價值。多測資（≤ 10 組）。

線段樹節點設計：純色標記

struct Node {
    int l, r;   // 區間範圍
    int s;      // 狀態：-1=雜色(混合), 1/2/3=純色(對應金屬值)
} t[MAXN << 2];

關鍵洞察：區間賦值後，該區間變為「純色」，子孫節點無需遞歸更新，只需在父節點打標記 s = color。查詢時遇到純色節點直接按長度×值計算，這就是懶標記的簡化形式（因只有賦值操作，無增量）。

建樹：初始全銅

void build(int l, int r, int num) {
    t[num].l = l; t[num].r = r; t[num].s = 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, num << 1);
    build(mid + 1, r, num << 1 | 1);
}

區間更新：下推純色標記

void update(int l, int r, int m, int num) {
    if (t[num].s == m) return; // 已是目標顏色，剪枝
    
    if (t[num].l == l && t[num].r == r) { // 完全覆蓋
        t[num].s = m;
        return;
    }
    
    // 當前節點是純色，需下推給子節點
    if (t[num].s != -1) {
        t[num<<1].s = t[num<<1|1].s = t[num].s;
        t[num].s = -1; // 父節點變雜色
    }
    
    int mid = (t[num].l + t[num].r) >> 1;
    if (l > mid) update(l, r, m, num << 1 | 1);
    else if (r <= mid) update(l, r, m, num << 1);
    else {
        update(l, mid, m, num << 1);
        update(mid + 1, r, m, num << 1 | 1);
    }
}

區間求和：遇純色直接算

int query(int num) {
    if (t[num].s != -1) // 純色
        return (t[num].r - t[num].l + 1) * t[num].s;
    // 雜色：遞歸查詢左右子樹
    return query(num << 1) + query(num << 1 | 1);
}

主流程

int main() {
    int T, n, k, x, y, z, cas = 1;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        build(1, n, 1);
        while (k--) {
            scanf("%d%d%d", &x, &y, &z);
            update(x, y, z, 1);
        }
        printf("Case %d: The total value of the hook is %d.\n", cas++, query(1));
    }
    return 0;
}

複雜度與技巧總結

• 建樹 O(N)，單次更新/查詢 O(log N)，總 O((N+Q) log N)
• 純色標記 替代傳統懶標記陣列，代碼極簡
• 剪枝：if (t[num].s == m) return; 避免無效下推
• 下推時機：只有當純色父節點需要部分更新時，才將顏色下推給子節點

此題是「線段樹 + 懶標記（純色標記）」的入門最佳範例，掌握後可無縫過渡到區間加法、區間最大值等更複雜的懶標記場景。