首页 学习笔记

虽然很久之前学过一遍，但是又忘了 QwQ，于是重新复习了一遍。

CDQ 分治是一个离线算法，也只能用于离线问题的处理上。

# 主要思想

把当前区间分成两半，向下递归处理。

左边和右边独立的贡献计算出来之后，再计算左边对右边的贡献。

通常会套上一些树状数组之类的数据结构（不然和暴力有啥区别 QwQ）

# 例题

板子题：P3810 【模板】三维偏序（陌上花开）

# Solution

先按第一维从小到大排序，对于区间 (l,r)(l, r)，递归处理 (l,mid)(l, mid) 和 (mid+1,r)(mid + 1, r)。

由于已经按照 aa 排过序，所以左边的 aa 一定不大于右边的 aa，就不用考虑了。

对于当前区间 (l,r)(l, r)，再对第二维 bb 从小到大排序。

然后这题就是普通的逆序对问题了，拿两个指针 ii 和 jj 分别扫两段区间 (l,mid)(l, mid) 和 (mid+1,r)(mid + 1, r)。把 Ci<=CjC_i <= C_j 的点插到树状数组里，再 query 统计答案。

# Code

mark
#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1e5 + 10;
const int K = 2e5 + 10;
struct ${
    int a, b, c, w, res;
}s[N];
int n, k, tot;
int ans[N];
inline bool cmp1($ x, $ y){
    return x.a != y.a ? x.a < y.a : (x.b != y.b ? x.b < y.b : x.c < y.c);
}
inline bool cmp2($ x, $ y){
    return x.b != y.b ? x.b < y.b : x.c < y.c;
}
int c[K];
inline void add(int x, int y){
    for(; x <= k; x += x & (-x)) c[x] += y;
}
inline int query(int x){
    int res = 0;
    for(; x; x -= x & (-x)) res += c[x];
    return res;
}
inline void CDQ(int l, int r){
    if(l == r) return;
    int mid = (l + r) >> 1;
    CDQ(l, mid), CDQ(mid + 1, r);
    sort(s + l, s + mid + 1, cmp2);
    sort(s + mid + 1, s + r + 1, cmp2);
    int i = l, j = mid + 1;
    while(j <= r){
        while(s[i].b <= s[j].b && i <= mid)
            add(s[i].c, s[i].w), i++;
        s[j].res += query(s[j].c), j++;
    }
    for(j = l; j < i; ++j) add(s[j].c, -s[j].w);
}
int main(){
    n = read(), k = read();
    for(int i = 1; i <= n; ++i)
        s[i] = ($){read(), read(), read()};
    sort(s + 1, s + 1 + n, cmp1);
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        cnt++;
        if(s[i].a != s[i + 1].a || s[i].b != s[i + 1].b || s[i].c != s[i + 1].c)
            s[++tot] = s[i], s[tot].w = cnt, cnt = 0;
    }
    CDQ(1, tot);
    for(int i = 1; i <= tot; ++i)
        ans[s[i].res + s[i].w - 1] += s[i].w;
    for(int i = 0; i < n; ++i) write(ans[i]), puts("");
    return 0;
}
_EOF_\_EOF\_