BZOJ 3262 陌上花開：CDQ 分治三維偏序計數

問題建模

N 朵花，每朵有三屬性 (x, y, z)。花 A 比花 B 美麗 ⇔ A.x ≥ B.x 且 A.y ≥ B.y 且 A.z ≥ B.z（至少一個嚴格大）。花的評級 = 比它不美麗的花的數量。求評級為 0..N-1 的花各有多少朵。N ≤ 10⁵。

等價於：對每朵花，計算有多少花在三維空間中被它支配（非嚴格支配）。這是經典三維偏序問題。

CDQ 分治核心思想

CDQ 分治將多維偏序轉化為一維排序 + 一維分治 + 一維數據結構：

1. 第一維排序：按 x 升序（x 相同按 y 升序，再按 z 升序）。
2. 第二維 CDQ 分治：對序列遞歸分治，合併時按 y 歸併排序，保證左半部分 y ≤ 右半部分 y。
3. 第三維樹狀數組：合併過程中，左半部花更新 BIT（在位置 z 加上 cnt），右半部花查詢 BIT 前綴和（≤ z），累加到答案。

關鍵細節：相同花的合併處理

若多朵花 (x,y,z) 完全相同，它們互相「美麗」（非嚴格支配）。需先將相同三元組合併，記錄出現次數 cnt。答案計算時，同組花互相貢獻 cnt-1（自身不計）。

算法流程

1. 讀入花屬性，按 (x,y,z) 排序。
2. 合併相同三元組 → 結構體 {x,y,z,cnt,ans}，新數組大小 M ≤ N。
3. CDQ(1, M)：
   if l==r: ans += cnt-1; return
   mid = (l+r)/2
   CDQ(l, mid)
   // 合併階段：左右半部按 y 歸併
   用臨時數組按 y 排序左右兩半
   初始化 BIT（用時間戳清零優化）
   雙指針掃描：
     若左半部 y ≤ 右半部 y：BIT.add(z, cnt), 指針++
     否則：右半部 ans += BIT.query(z), 指針++
   清理 BIT（時間戳法 O(1)）
   CDQ(mid+1, r)
   // 歸併排序按 y 合併左右半部，供下層使用
   merge_by_y(l, mid, r)

樹狀數組時間戳優化

int bit[MAXZ], tim[MAXZ], T = 0;
void add(int x, int v) {
    for (; x <= maxZ; x += x&-x) {
        if (tim[x] != T) bit[x] = 0, tim[x] = T;
        bit[x] += v;
    }
}
int query(int x) {
    int res = 0;
    for (; x; x -= x&-x) if (tim[x] == T) res += bit[x];
    return res;
}
// 每次合併前 ++T，自動清零

複雜度分析

• 排序：O(N log N)
• CDQ 分治：O(M log M) 層，每層歸併 + BIT 操作 O(M log Z)，總 O(M log M log Z)
• Z 經離散化 ≤ M，故 O(N log² N)，N=10⁵ 極快。

總結

BZOJ 3262 是 CDQ 分治解決三維偏序的標桿題。核心模式：排序一維 + CDQ 分治二維 + BIT 三維。關鍵實現細節包括：相同點合併計數、BIT 時間戳清零、歸併排序保持 y 有序。掌握此模板，可解決所有「多維偏序計數/求和」問題。