HDU 4509 湫湫減肥記 II：線段樹統計可用鍛煉時間

問題描述

一天 24 小時 = 1440 分鐘。給定 n 個已安排事件的起止時間（HH:MM），事件可能重疊。求未被任何事件佔用的總分鐘數，即可用於鍛煉的時間。n ≤ 500,000，需快速 IO。

線段樹方案

將 1440 分鐘離散化為 0..1439 的葉子節點。每個事件 [start, end) 對應區間更新（標記佔用）。最終查詢未被標記的葉子數。
- 區間更新：將 [l, r] 標記為佔用（懶標記 `flag` 表示整段已滿）。
- 查詢：遞歸統計未滿段的葉子數。
- 時間：每次更新/查詢 O(log 1440) ≈ O(11)，總 O(n log T) 極快。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2000;

struct Node {
    int lson, rson;
    bool flag;
    int mid() { return (lson + rson) >> 1; }
} tree[maxn * 4];

void pushUp(int rt) {
    tree[rt].flag = tree[rt << 1].flag && tree[rt << 1 | 1].flag;
}

void build(int L, int R, int rt) {
    tree[rt].lson = L;
    tree[rt].rson = R;
    tree[rt].flag = false;
    if (L == R) return;
    int mid = tree[rt].mid();
    build(L, mid, rt << 1);
    build(mid + 1, R, rt << 1 | 1);
}

void update(int L, int R, int l, int r, int rt) {
    if (tree[rt].flag) return;
    if (L <= l && R >= r) {
        tree[rt].flag = true;
        return;
    }
    int mid = tree[rt].mid();
    if (L <= mid) update(L, R, l, mid, rt << 1);
    if (R > mid) update(L, R, mid + 1, r, rt << 1 | 1);
    pushUp(rt);
}

int query(int L, int R, int l, int r, int rt) {
    if (tree[rt].flag) return r - l + 1;
    if (l == r) return 0;
    int mid = tree[rt].mid();
    int ret = 0;
    if (L <= mid) ret += query(L, R, l, mid, rt << 1);
    if (R > mid) ret += query(L, R, mid + 1, r, rt << 1 | 1);
    return ret;
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        build(0, 1439, 1);
        while (n--) {
            int a, b, c, d;
            scanf("%d:%d %d:%d", &a, &b, &c, &d);
            update(a * 60 + b + 1, c * 60 + d, 0, 1439, 1);
        }
        printf("%d\n", 1440 - query(0, 1439, 0, 1439, 1));
    }
    return 0;
}

關鍵細節

• 時間轉換：`HH*60 + MM`，範圍 0..1439。
• 區間邊界：題目給定起止時間，假設事件佔用 [start+1, end] 分鐘？代碼中 `a*60+b+1` 到 `c*60+d`，需確認題目定義。樣例驗證通過說明此處理正確。
• 懶標記 `flag`：一旦節點標記為全滿，子孫無需再更新/查詢，大幅加速。
• 大量輸入：使用 `scanf`，避免 `cin` 慢。

替代方案：差分數組

因時間軸固定 1440，更簡單做法：
`diff[start+1]++`, `diff[end+1]--`，前綴和得每分鐘佔用計數，掃描計數為 0 的分鐘數。O(n + T)，代碼更短，無需線段樹。但線段樹練習價值大，適合區間動態增刪場景。

總結

線段樹經典應用：固定小範圍區間覆蓋統計。懶標記優化批量更新，查詢時利用 `flag` 剪枝。注意邊界處理與快速 IO。