CDQ分治

CDQ分治大致有 3 种用法

解决和点对有关的问题

1. 找到序列的重点 $mid$
2. 将所有点对 $(i,j)$ 分成 3 类
   • a. $1\le i\le mid,1\le j\le mid$
   • b. $1\le i\le mid,mid+1\le j\le n$
   • c. $mid+1\le i\le n,mid+1\le j\le n$
3. 第一类和第三类点对递归处理
4. 设法处理第二类点对

例题：三维偏序

#include <bits/stdc++.h>
using namespace std;

struct Question {
    int id, x, y, z, cnt, ans;
    Question() : id(0), x(0), y(0), z(0), cnt(0), ans(0) {}
    Question(int id, int x, int y, int z) : id(id), x(x), y(y), z(z), cnt(0), ans(0) {}
};

struct Tree {
    int MAXN;
    vector<int> c;
    void init(int n) {
        MAXN = n + 1;
        c.resize(MAXN);
        fill(c.begin(), c.end(), 0);
    }

    void add(int x, int v) {
        for (; x < MAXN; x += x & -x) {
            c[x] += v;
        }
    }

    int get(int x) {
        int sum = 0;
        for (; x > 0; x -= x & -x) {
            sum += c[x];
        }
        return sum;
    }
};

bool cmp1(Question a, Question b) {
    return (a.x < b.x) || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.z < b.z);
}

bool cmp2(Question a, Question b) {
    return (a.y < b.y) || (a.y == b.y && a.z < b.z);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, k;  cin >> n >> k;
    vector<Question> q(n + 1);
    int M = 0;
    for (int i = 1; i <= n; i++) {
        int x, y, z; cin >> x >> y >> z ;
        M = max({M, x, y, z});
        q[i] = Question(i, x, y, z);
    }
    vector<Question> qb(n + 1);
    Tree tree; tree.init(k + 1);
    int num = 0;
    sort(q.begin() + 1, q.end(), cmp1);
    for (int i = 1; i <= n; i++) {
        if (i != 1 && q[i].x == q[i - 1].x && q[i].y == q[i - 1].y && q[i].z == q[i - 1].z) {
            qb[num].cnt += 1;
        }
        else {
            num += 1;
            qb[num].x = q[i].x; qb[num].y = q[i].y; qb[num].z = q[i].z; qb[num].cnt = 1;
        }
    }

    qb.resize(num + 1);

    auto cdq = [&] (auto && cdq, int l, int r) {
        int mid = (l + r) >> 1;
        if (l == r) return;
        cdq(cdq, l, mid); cdq(cdq, mid + 1, r);

        sort(qb.begin() + l, qb.begin() + mid + 1, cmp2);
        sort(qb.begin() + mid + 1, qb.begin() + r + 1, cmp2);

        stack<int> st;
        for (int i = l, j = mid + 1; j <= r; j++) {
            while (i <= mid && qb[i].y <= qb[j].y)  {
                tree.add(qb[i].z, qb[i].cnt);
                st.push(i);
                i += 1;
            }
            qb[j].ans += tree.get(qb[j].z);
        }

        while (!st.empty()) {
            int i = st.top(); st.pop();
            tree.add(qb[i].z, -qb[i].cnt);
        }
    };

    cdq(cdq, 1, num);

    // for (int i = 1; i <= num; i++) {
    //     cout << qb[i].x << ' ' << qb[i].y << ' ' << qb[i].z << ' ' << qb[i].cnt << ' ' << qb[i].ans << '\n';
    // }

    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= num; i++) {
        ans[qb[i].ans + qb[i].cnt - 1] += qb[i].cnt;
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] << '\n';
    
    return 0;
}

CDQ 分治优化 1D/1D 动态规划的转移

处理这一类问题时，需要先处理 solve(l,mid)，然后处理 $l\le j\le mid,mid+1\le j\le r$ 的点对，最后处理 solve(mid+1,r)

而三位偏序中，不需要考虑这个问题

原因是 DP 的转移必须是有序的

将动态问题转化为静态问题

前两种方法中，CDQ分治的目的是将序列之后递归处理点对之间的关系。这一类做法是将时间序列进行拆分

我们先递归处理 $(l,mid)(mid+1,r)$ 之间的修改-询问关系，然后处理 $l\le i\le mid,mid+1\le j\le r$ 的修改-询问关系

• 注意，如果修改是非独立的话，例如赋值操作，那么第二类就要放在一三类之中，和 1D 动态规划的优化一样