CDQ分治

CDQ分治は、マージソートを応用した分割統治アルゴリズムであり、特に多次元の順序制約（偏序）問題に有効である。基本的な流れは以下の通り：

1. 左半分と右半分をそれぞれ再帰的に処理。
2. 左右をマージしながら、左側の要素が右側の要素に与える影響を計算。

3次元偏序問題

各点が3つの属性 (a, b, c) を持つとき、ある点よりすべての属性が小さい点の数を求める問題。以下のように処理する：

• 第1次元でソート。
• 再帰中に第2次元でマージ。
• 第3次元についてはFenwick木（BIT）で管理し、クエリ時に累積和を取得。

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

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

void cdq(int l, int r, vector<Point>& pts, vector<long long>& res, Fenwick& bit) {
    if (l == r) {
        res[pts[l].idx] += pts[l].cnt;
        return;
    }
    int mid = (l + r) / 2;
    cdq(l, mid, pts, res, bit);
    cdq(mid + 1, r, pts, res, bit);

    vector<Point> tmp;
    int i = l, j = mid + 1;

    while (i <= mid && j <= r) {
        if (pts[i].y <= pts[j].y) {
            bit.add(pts[i].z, pts[i].cnt);
            tmp.push_back(pts[i++]);
        } else {
            res[pts[j].idx] += bit.sum(pts[j].z);
            tmp.push_back(pts[j++]);
        }
    }

    while (i <= mid) {
        bit.add(pts[i].z, pts[i].cnt);
        tmp.push_back(pts[i++]);
    }

    while (j <= r) {
        res[pts[j].idx] += bit.sum(pts[j].z);
        tmp.push_back(pts[j++]);
    }

    for (int k = l; k <= mid; ++k)
        bit.add(pts[k].z, -pts[k].cnt);

    for (int k = l; k <= r; ++k)
        pts[k] = tmp[k - l];
}

4次元偏序

CDQをネストして対応。外側のCDQで第1次元を固定し、内側のCDQで第2次元を処理。第3・4次元はBITなどで扱う。計算量は O(n log³n)。

全体二分法（オフライン全体二分）

全体二分法は、値域に関する二分探索を複数のクエリに対して同時に行う手法。主に「動的K番目の要素」や「イベントベースの到達判定」などに適用される。

動的K番目の要素（Dynamic Rankings）

操作をオフラインで収集し、値域を二分しつつ、各操作を「値がmid以下か否か」で分割。BITで現在の区間内の要素数を管理。

struct Op {
    int type; // 0: query, 1/-1: add/remove
    int pos, val, k, id;
};

void solve(int low, int high, vector<Op>& ops, vector<int>& ans, Fenwick& bit) {
    if (ops.empty()) return;
    if (low == high) {
        for (auto& op : ops)
            if (op.type == 0) ans[op.id] = low;
        return;
    }

    int mid = (low + high) / 2;
    vector<Op> left_ops, right_ops;

    for (auto& op : ops) {
        if (op.type == 0) {
            int cnt = bit.range_sum(op.pos, op.val);
            if (op.k <= cnt) {
                left_ops.push_back(op);
            } else {
                op.k -= cnt;
                right_ops.push_back(op);
            }
        } else {
            if (op.val <= mid) {
                bit.add(op.pos, op.type);
                left_ops.push_back(op);
            } else {
                right_ops.push_back(op);
            }
        }
    }

    // BITのクリア（left_ops中の更新のみ）
    for (auto& op : left_ops)
        if (op.type != 0) bit.add(op.pos, -op.type);

    solve(low, mid, left_ops, ans, bit);
    solve(mid + 1, high, right_ops, ans, bit);
}

イベント到達時間の最小化（MET-Meteors）

各色が目標値に到達する最小のイベント番号を求める。全体二分の際に、BITの状態を動的に維持することで高速化。現在のイベント位置を指すポインタを前後に移動し、不要なクリアを回避。

void solve(int L, int R, vector<Query>& qs, vector<int>& ans, Fenwick& bit, int& ptr, const vector<Event>& events) {
    if (qs.empty()) return;
    if (L == R) {
        for (auto& q : qs) ans[q.id] = L;
        return;
    }

    int mid = (L + R) / 2;
    while (ptr < mid) bit.apply(events[++ptr]), ptr++;
    while (ptr > mid) bit.undo(events[ptr--]);

    vector<Query> left_qs, right_qs;
    for (auto& q : qs) {
        long long total = 0;
        for (int pos : q.positions) {
            total += bit.sum(pos);
            if (total >= q.target) break;
        }
        if (total >= q.target)
            left_qs.push_back(q);
        else
            right_qs.push_back(q);
    }

    solve(L, mid, left_qs, ans, bit, ptr, events);
    solve(mid + 1, R, right_qs, ans, bit, ptr, events);
}

2次元K番目の要素

2次元BITを使用するが、クリア処理には注意が必要。ゼロクリアではなく、差分による復元が望ましい。誤ったクリアは未定義動作を引き起こす可能性がある。