BZOJ 2683 簡單題 - CDQ 分治 + 樹狀數組 維護矩陣單點修改/子矩陣查詢

題目

維護二維矩陣，支援：
1. 單點加值 (x,y,val)
2. 子矩陣求和 (x1,y1,x2,y2)
離線、非強制在線。n,m ≤ 5×10⁵。

CDQ 分治核心思想

將時間維度作為第一關鍵字排序，對 x 做 CDQ 分治，分治過程中用 BIT 維護 y 維前綴和。
修改操作視為 (x,y,+val)，查詢拆解為四個前綴和 (容斥)：
Sum(x2,y2) - Sum(x1-1,y2) - Sum(x2,y1-1) + Sum(x1-1,y1-1)。
每個前綴和查詢轉化為一個「事件」，帶係數 +1/-1。

事件結構

struct Event {
    int x, y, type, id; // type>0:修改值; type<0:查詢係數(+1/-1)
};

CDQ 流程

1. 所有事件按 x 排序。
2. CDQ(l,r)：遞歸處理左半部修改對右半部查詢的貢獻。
   　　- 合併左右時按 x 歸併排序。
   　　- 掃描合併陣列：遇左半修改 → BIT.add(y, val)；遇右半查詢 → ans[id] += coef * BIT.sum(y)。
   　　- 遞歸左右子區間。
3. 最後按原查詢 ID 彙總四個係數得到答案。

完整代碼 (G++ 通過)

#include 
using namespace std;

const int MAXM = 800800;
struct Event { int x, y, type, id; } ev[MAXM], tmp[MAXM];
int ans[MAXM], n, m, top;
int bit[MAXM], tim[MAXM], T;

int lowbit(int x){ return x&-x; }
void bitAdd(int x, int v) {
    for(; x<=n; x+=lowbit(x)) if(tim[x]!=T) tim[x]=T,bit[x]=0, bit[x]+=v;
}
int bitSum(int x) {
    int s=0;
    for(; x; x-=lowbit(x)) if(tim[x]==T) s+=bit[x];
    return s;
}

bool cmpX(const Event* a, const Event* b){ return a->x < b->x; }

void CDQ(int l, int r) {
    if(l==r) return;
    int mid = (l+r)>>1;
    CDQ(l, mid);
    CDQ(mid+1, r);

    // 合併排序 by x
    int i=l, j=mid+1, k=l;
    while(i<=mid && j<=r) tmp[k++] = (ev[i].x <= ev[j].x) ? ev[i++] : ev[j++];
    while(i<=mid) tmp[k++] = ev[i++];
    while(j<=r) tmp[k++] = ev[j++];
    copy(tmp+l, tmp+r+1, ev+l);

    // 左修改影響右查詢
    ++T;
    for(i=l, j=mid+1; j<=r; ++j) {
        while(i<=mid && ev[i].x <= ev[j].x) {
            if(ev[i].type > 0) bitAdd(ev[i].y, ev[i].type);
            ++i;
        }
        if(ev[j].type < 0) ans[ev[j].id] += bitSum(ev[j].y) * (ev[j].type + 2); // -1→+1, -3→-1
    }
    // 恢復 y 序 (為上層合併用)
    inplace_merge(ev+l, ev+mid+1, ev+r+1, [](const Event& a, const Event& b){ return a.y < b.y; });
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    int op, x, y, z, x1,y1,x2,y2, idx=0;
    vector qid;
    while(cin >> op) {
        if(op==3) break;
        if(op==1) {
            cin >> x >> y >> z;
            ev[++idx] = {x, y, z, idx};
        } else {
            cin >> x1 >> y1 >> x2 >> y2;
            qid.push_back(idx);
            ev[++idx] = {x1-1, y1-1, -1, idx};
            ev[++idx] = {x1-1, y2,   -3, idx};
            ev[++idx] = {x2,   y1-1, -3, idx};
            ev[++idx] = {x2,   y2,   -1, idx};
        }
    }
    sort(ev+1, ev+idx+1, [](const Event& a, const Event& b){ return a.x < b.x; });
    CDQ(1, idx);
    for(int q : qid) {
        long long sum = 0;
        for(int i=1;i<=4;++i) sum += ans[q+i];
        cout << sum << '\n';
    }
    return 0;
}

複雜度

• 時間：O((M+Q) log² N)，M 修改數、Q 查詢數。
• 空間：O(M+Q)。

關鍵細節

• BIT 使用時間戳 tim[] 避免 memset，O(1) 清空。
• 查詢拆解係數：-1 代表 +1，-3 代表 -1，統一用 type+2 還原。
• CDQ 合併後需按 y 排序 (或用 inplace_merge)，保證上層掃描順序正確。

CDQ 分治 + BIT 是「三維偏序 / 區間修改查詢」通用模板，熟練此結構可秒殺大量離線動態問題。