BZOJ 1176 Mokia：CDQ 分治解決二維動態區間加點查區間和

問題抽象

W×W 矩陣（W≤2e6），初始值 S（實為 0）。M≤160000 次點加操作，Q≤10000 次子矩陣求和查詢。離線處理，輸出每次查詢結果。

CDQ 分治核心思想

將修改與查詢按時間順序混合為一個序列。每個查詢拆為 4 個前綴和查詢（容斥原理）。CDQ 遞歸處理時間區間 [l, r]：

• 遞歸解決左半部 [l, mid] 內部查詢。
• 處理左半部修改對右半部查詢的貢獻：按 x 座標排序，用一維 BIT 維護 y 軸前綴和，掃描線更新並查詢。
• 遞歸解決右半部 [mid+1, r]。
• 歸併按 x 排序以保證上層有序性。

關鍵數據結構

• struct Node { int x, y, val, time, type; }：type=0 修改，type=1 查詢子項。
• BIT 數組 c[] 配合時間戳 tim[] 實現 O(1) 清零（避免每次 memset）。

代碼流程

void CDQ(int l, int r) {
    if (l==r) return;
    int mid = (l+r)>>1;
    CDQ(l, mid);
    // 左修改 -> 右查詢
    sort(q+l, q+mid+1, cmp_x);
    sort(q+mid+1, q+r+1, cmp_x);
    ++T; // 時間戳
    int i=l, j=mid+1;
    while (j<=r) {
        while (i<=mid && q[i].x <= q[j].x) {
            if (q[i].type==0) bit.add(q[i].y, q[i].val);
            ++i;
        }
        if (q[j].type==1) q[j].ans += bit.query(q[j].y);
        ++j;
    }
    CDQ(mid+1, r);
    // 歸併按 x 排序
    merge(q+l, q+mid+1, q+mid+1, q+r+1, tmp, cmp_x);
    copy(tmp, tmp+r-l+1, q+l);
}

主程序讀入操作，修改直接存入，查詢拆 4 個子項存入，按時間排序後調用 CDQ，最後按原查詢順序組合 4 子項輸出答案。