HDU 1698 區間更新線段樹：懶惰標記實現區間賦值求和

題目大意

初始長度 n 數組全為 1。m 次操作：將區間 [a,b] 賦值為 c。最後求總和。多組測試數據。

懶惰標記機制

• sum[node]：該區間總和
• tag[node]：待下推的賦值標記（0 表示無）
• 下推時：子節點 sum = tag * 子區間長度，tag = tag

關鍵函數

void pushdown(int node, int len) {
    if (tag[node]) {
        tag[node<<1] = tag[node<<1|1] = tag[node];
        sum[node<<1] = tag[node] * (len - (len>>1));
        sum[node<<1|1] = tag[node] * (len>>1);
        tag[node] = 0;
    }
}

void update(int L, int R, int val, int l, int r, int node) {
    if (L <= l && r <= R) {
        tag[node] = val;
        sum[node] = val * (r - l + 1);
        return;
    }
    pushdown(node, r - l + 1);
    int mid = (l+r)>>1;
    if (L <= mid) update(L, R, val, l, mid, node<<1);
    if (R > mid) update(L, R, val, mid+1, r, node<<1|1);
    sum[node] = sum[node<<1] + sum[node<<1|1];
}

構建與查詢

構建遞歸初始化葉子為 1。最終答案即 sum[1]（根節點總和），無需額外查詢函數。

複雜度

單次更新 O(log n)，m 次 O(m log n)。n,m ≤ 10⁵ 完全足夠。空間 4n。

樣例輸出格式

Case 1: The total value of the hook is 123.