SDUT 2880：線段樹區間加/賦值/查詢綜合應用

題目大意

有 r 行 c 列的網格，初始值 0。m 次操作，每次在時刻 t 對子矩形 (l,r) 進行「查詢當前值並歸零」。實際上是區間加法（時間增量）與區間賦值（歸零）交替。求所有查詢值之和。

線段樹維護

對每行獨立建立線段樹（或二維壓平為一維）。每個節點維護：

• sum：區間和
• max, min：區間極值（本題可能不需要）
• add：區間加法懶標記
• set：區間賦值懶標記（-1 表示無）

懶標記下推優先級

set 優先級高於 add。下推時：

1. 若父節點有 set，直接覆蓋子節點的 set 和 add。
2. 再應用父節點的 add 到子節點。

關鍵代碼片段

void pushDown(int rt) {
    if (tree[rt].set != -1) {
        // 覆蓋子節點
        tree[ls].set = tree[rs].set = tree[rt].set;
        tree[ls].add = tree[rs].add = 0;
        tree[ls].sum = (tree[ls].r - tree[ls].l + 1) * tree[rt].set;
        tree[rs].sum = (tree[rs].r - tree[rs].l + 1) * tree[rt].set;
        tree[rt].set = -1;
    }
    if (tree[rt].add) {
        int v = tree[rt].add;
        tree[ls].add += v; tree[rs].add += v;
        tree[ls].sum += v * (tree[ls].r - tree[ls].l + 1);
        tree[rs].sum += v * (tree[rs].r - tree[rs].l + 1);
        tree[rt].add = 0;
    }
}

操作流程

1. 按時間排序所有操作。
2. 對每次操作：先區間加 (t - prev_t)（時間流逝增量），再查詢區間和累加到答案，最後區間賦值 0。

錯誤修正

初始代碼中 update_add 寫成所有節點 +1，應為 +tr（時間差）。修正後 AC。

總結

本題是線段樹雙標記（加法+賦值）經典綜合題：時間流逝對應區間加法，查詢歸零對應區間賦值+查詢和。關鍵在於懶標記下推順序（set 先於 add）與正確處理時間增量。代碼量較大，需仔細調試。