BZOJ 3932 詳解：可持久化線段樹解決任務優先級區間查詢

算法流程

1. 優先級離散化：收集所有 P_i，排序去重映射到 [1..sz]
2. 構建事件：每任務生成 (S, +1, pid) 和 (E+1, -1, pid)
3. 按時間排序事件
4. 掃描 t = 1..n：
   • 從版本 t-1 克隆，應用時刻 t 的所有事件（點更新 ±1）
   • 得到版本 t 的線段樹根 rt[t]
5. 查詢：在 rt[X_i] 上查詢前 K_i 小和

線段樹節點設計

struct Node {
    int lc, rc;      // 左右子節點索引
    int cnt;         // 區間內任務數
    long long sum;   // 區間內優先級和
} tr[MAXM];
int rt[MAXN], tot = 0;
int P[MAXN];  // 離散化後優先級值

關鍵操作

建樹

void build(int& o, int l, int r) {
    o = ++tot;
    tr[o].cnt = tr[o].sum = 0;
    if (l == r) return;
    int mid = (l+r)>>1;
    build(tr[o].lc, l, mid);
    build(tr[o].rc, mid+1, r);
}

持久化更新

void update(int pre, int& cur, int l, int r, int pos, int delta) {
    cur = ++tot;
    tr[cur] = tr[pre];  // 復用舊節點
    tr[cur].cnt += delta;
    tr[cur].sum += 1LL * delta * P[pos];
    if (l == r) return;
    int mid = (l+r)>>1;
    if (pos <= mid) update(tr[pre].lc, tr[cur].lc, l, mid, pos, delta);
    else update(tr[pre].rc, tr[cur].rc, mid+1, r, pos, delta);
}

查詢前 K 小和

long long query(int o, int l, int r, int k) {
    if (k == 0) return 0;
    if (l == r) return 1LL * P[l] * k;  // 或 tr[o].sum / tr[o].cnt * k
    int mid = (l+r)>>1;
    if (tr[tr[o].lc].cnt >= k) 
        return query(tr[o].lc, l, mid, k);
    else 
        return tr[tr[o].lc].sum + query(tr[o].rc, mid+1, r, k - tr[tr[o].lc].cnt);
}

完整主流程

int main() {
    int m = read(), n = read();
    // 讀取任務，離散化優先級
    // 構建事件，按時間排序
    build(rt[0], 1, sz);
    int evtPtr = 0;
    for (int t = 1; t <= n; ++t) {
        rt[t] = rt[t-1];
        while (evtPtr < events.size() && events[evtPtr].time == t) {
            update(rt[t], rt[t], 1, sz, events[evtPtr].pid, events[evtPtr].delta);
            ++evtPtr;
        }
    }
    long long pre = 1;
    for (int i = 1; i <= n; ++i) {
        int X = read(), A = read(), B = read(), C = read();
        int K = 1 + (1LL*A*pre + B) % C;
        long long ans = (K >= tr[rt[X]].cnt) ? tr[rt[X]].sum : query(rt[X], 1, sz, K);
        printf("%lld\n", ans);
        pre = ans;
    }
}

關鍵細節與避坑

1. 事件時間 E+1：任務在 E 秒仍運行，E+1 才移除
2. 離散化去重：相同優先級映射同一索引
3. 長長整型：優先級和可能達 10⁵ × 10⁷ = 10¹²，需 long long
4. 節點數估算：(m×2 + n) × log(sz) ≈ 200000 × 17 ≈ 340 萬，開 800 萬 安全
5. 查詢邊界：K=0 返回 0；K ≥ 總數 返回總和

複雜度分析

• 構建：O((m+n) log m)
• 查詢：O(log m)
• 空間：O((m+n) log m)

總結

BZOJ 3932 是可持久化線段樹的標準應用：「時間維度版本化 + 優先級權值線段樹 + 前 K 小查詢」。關鍵技巧：事件掃描線構建版本、離散化權值、節點存 cnt/sum 支援前 K 小和查詢。可持久化線段樹是「歷史版本查詢」問題的通用利器，掌握此模板可解決區間第 K 小、區間前 K 小和、區間眾數等經典問題。