基本概念

cdq分治法は分割統治アルゴリズムの一種で、多次元空間における点対関係の処理に特化しています。主な処理手順は以下の通りです：

1. 区間[l, r]を中央値mで分割
2. 左半分[l,m]と右半分[m+1,r]それぞれの再帰処理
3. 境界をまたぐ点対の処理（主にBITやセグメント木で実装）

応用例

三次元部分順序問題

次元ごとにソートと統計処理を組み合わせる方法を示します：

struct Point {
    int x, y, z;
};

bool compareY(const Point& a, const Point& b) {
    if(a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}

void process(int left, int right) {
    if(left == right) return;
    int mid = (left + right) / 2;
    process(left, mid);
    process(mid+1, right);
    
    sort(points+left, points+mid+1, compareY);
    sort(points+mid+1, points+right+1, compareY);
    
    int idx = left;
    for(int i = mid+1; i <= right; i++) {
        while(idx <= mid && points[idx].y <= points[i].y) {
            updateBIT(points[idx].z, 1);
            idx++;
        }
        count[i] += queryBIT(points[i].z);
    }
    // 後処理（BITの状態を戻す）
}

動的計画法の最適化

次のような状態遷移式を持つDP問題に適用可能です：

dp[i] = max(dp[j] * (条件式))

例：最長非増加部分列の計算

void optimizeDP(int left, int right) {
    if(left == right) return;
    int mid = (left + right) / 2;
    optimizeDP(left, mid);
    
    // ソートとクエリ処理
    auto comp = [](const Data& a, const Data& b){
        return a.param < b.param;
    };
    sort(data+left, data+mid+1, comp);
    sort(data+mid+1, data+right+1, comp);
    
    int ptr = left;
    for(int i = mid+1; i <= right; i++) {
        while(ptr <= mid && data[ptr].x <= data[i].x) {
            update(data[ptr].y, data[ptr].value);
            ptr++;
        }
        dp[i] = max(dp[i], query(data[i].y));
    }
}

四次元順序問題の処理

cdq分治法を二重に適用する手法：

struct Operation {
    int t, x, y, z;
    // メンバ変数省略
};

void innerCDQ(int l, int r) {
    if(l >= r) return;
    int mid = (l + r) / 2;
    innerCDQ(l, mid);
    innerCDQ(mid+1, r);
    
    // 第三・第四次元の処理
    mergeAndCount();
}

void outerCDQ(int l, int r) {
    if(l >= r) return;
    int mid = (l + r) / 2;
    outerCDQ(l, mid);
    outerCDQ(mid+1, r);
    
    // 第二次元のソート
    sort(data+mid+1, data+r+1, byY);
    // 内部CDQ呼び出し
    innerCDQ(1, currentSize);
}

計算量分析

• 基本パターン：O(n log²n)
• 多重適用時：O(n log³n)

各層の分割統治処理で次元数が増えるごとにlog nのオーバーヘッドが発生します。