CDQ分治小结

warning:此文仅用博主复习使用，初学者看的话后果自负。。

复习的时候才发现以前根本就没写过这种东西的总结，简单的扯一扯

cdq分治的经典应用就是解决偏序问题

比如最经典的三维偏序问题

给出\(n\)个数，每个数\(i\)，有三个属性\(a_i, b_i, c_i\)，现在我们要统计对于每个\(i\)，\(a_j \leqslant a_i, b_j \leqslant b_i, c_j \leqslant c_i\)的个数

显然我们可以先把所有数都按\(a_i\)排序一遍，这样考虑每个位置\(i\)的时候只需要考虑它前面的贡献即可

接下来我们递归处理区间\([1, N]\)。

设分治中心为\(mid\)，cdq分治的主要思想递归处理每一段区间，只考虑过分治中心的贡献。

同时，我们采用归并排序的思想，保证每一次统计答案的时候区间\([l, mid]\)和\([mid +1, r]\)内的元素的\(b_i\)都是相对有序的

这样我们只需要用两个指针扫一遍，同时用树状数组来维护一下\(c_i\)即可

好像说的挺抽象的，貌似直接看代码会好很多？

void CDQ(int l, int r) {

    if(l >= r) return ;//区间不合法

    int mid = l + r >> 1;

    CDQ(l, mid); CDQ(mid + 1, r);//递归下去处理子区间，处理完之后保证区间内的bi相对有序

    int nl = l, nr = mid + 1, top = l - 1, sum = 0;//使用两个指针来归并本区间

    while(nl <= mid || nr <= r) {//st数组记录的时把两端区间按bi大小合并后的值

        if((nr > r) || (nl <= mid && A[nl].b <= A[nr].b)) T.add(A[nl].c, A[nl].w), st[++top] = A[nl++];//用树状数组维护ci的贡献

        else A[nr].id += T.Query(A[nr].c ), st[++top] = A[nr++];//直接查询即可

    }

    for(int i = l; i <= mid; i++) T.add(A[i].c, -A[i].w);//把左边区间的影响消除

    for(int i = l; i <= r; i++) A[i] = st[i];//按bi排序

}

然而有一种非常恶心的情况：即\(a_i = a_j, b_i = b_j, c_i = c_j\)

他们内部的贡献往往是不好考虑的，一个最直观的想法是直接把这些相同的数看成一个，统计答案的时候直接加上他们的数量即可

模板

洛谷P3810 【模板】三维偏序（陌上花开）

#include<bits/stdc++.h>

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)

using namespace std;

const int MAXN = 2e5 + 10;

char buf[(1 << 22)], *p1 = buf, *p2 = buf;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

char obuf[1<<24], *O=obuf;

void print(int x) {

    if(x > 9) print(x / 10);

    *O++= x % 10 + '0';

}

int N, ans[MAXN];

struct Array {

    int a, b, c, id, w;

    bool operator == (const Array &rhs) const {

        return a == rhs.a && b == rhs.b && c == rhs.c;

    }

    bool operator < (const Array &rhs) const {

        return(a == rhs.a ? (b == rhs.b ? c < rhs.c : b < rhs.b) : a < rhs.a);

    }

}A[MAXN], st[MAXN];

struct Node {

#define lb(x) (x & (-x))

    int T[MAXN], Lim;

    void add(int x, int v) {

        while(x <= Lim) T[x] += v, x += lb(x);

    }

    int Query(int x) {

        int ans = 0;

        while(x) ans += T[x], x -= lb(x);

        return ans;

    }

}T;

void CDQ(int l, int r) {

    if(l >= r) return ;

    int mid = l + r >> 1;

    CDQ(l, mid); CDQ(mid + 1, r);

    int nl = l, nr = mid + 1, top = l - 1, sum = 0;

    while(nl <= mid || nr <= r) {

        if((nr > r) || (nl <= mid && A[nl].b <= A[nr].b)) T.add(A[nl].c, A[nl].w), st[++top] = A[nl++];

        else A[nr].id += T.Query(A[nr].c ), st[++top] = A[nr++];

    }

    for(int i = l; i <= mid; i++) T.add(A[i].c, -A[i].w);

    for(int i = l; i <= r; i++) A[i] = st[i];

}

int main() {

    N = read(); T.Lim = read();

    for(int i = 1; i <= N; i++) A[i].a = read(), A[i].b = read(), A[i].c = read(), A[i].w = 1;

    stable_sort(A + 1, A + N + 1);

    int num = 1;

    for(int i = 2; i <= N; i++){

        if(A[i] == A[num]) A[num].w++;

        else A[++num] = A[i];

    }

    CDQ(1, num);

    for(int i = 1; i <= num; i++) ans[A[i].id + A[i].w - 1] += A[i].w;

    for(int i = 0; i < N; i++) print(ans[i]), *O++ = '\n';

    fwrite(obuf, O-obuf, 1 , stdout);

    return 0;

}

巴特西

CDQ分治小结

CDQ分治小结

模板

最新文章

热门文章