cdq分治

发表于 | 分类于 ，

概述:

cdq分治是一类分治思想, 和整体二分类似, 在一些可离线的题目中可以替代一些复杂的数据结构.

cdq分治的一个重要思想是用一个子问题来计算另一个子问题的贡献.

以三维偏序为例:

实现:

与二维偏序一样, 首先需要按第一维进行排序, 保证第一维的有序.

由于第一维有序, 此时对整个区间进行分治, 将左区间的信息统计到右区间的贡献, 便可以消除第一维的影响.

同时由于已经进行了分治, 第二维可以使用归并排序, 统计第三维信息时使用树状数组即可.

至于这样分治为什么行:

从图中可以看出, 对于每一个点, 分治的过程相当于将这个点左边的区间分成了若干块, 合起来便是这个点左边区间的贡献.

需要注意原例题中需要去重.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Mn(100500),Mk(200500);

template<typename T>
void qrd(T& x) {
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c-'0';
        c = getchar();
    }
}

inline int lb(int x) {  //lowbit
    return x&-x;
}

int n,k;

struct trip {   //三维数点
    int x,y,z,w,ans;
    //三个维度, 重复次数, 偏序对数
    bool operator < (const trip& rhs) const {   //排序
        if(x==rhs.x) {
            if(y==rhs.y) {
                return z<rhs.z;
            }
            return y<rhs.y;
        }
        return x<rhs.x;
    }
    bool operator == (const trip& rhs) const {  //判重
        return x==rhs.x && y==rhs.y && z==rhs.z;
    }
    bool operator != (const trip& rhs) const {
        return !(*this == rhs);
    }
}atr[Mn],tmp[Mn];   //原数组, 临时数组

int ans[Mn],c[Mk];  //答案, 树状数组
void mdf(int mx,int mk) {   //修改
    while(mx<=k) {
        c[mx] += mk;
        mx += lb(mx);
    }
}
int qry(int qx) {   //查询
    int ret(0);
    while(qx) {
        ret += c[qx];
        qx -= lb(qx);
    }
    return ret;
}

void cdq(int l,int r) {     //cdq主过程
    if(l==r) {  //边界
        return;
    }
    int mid((l+r)/2);
    cdq(l,mid), cdq(mid+1,r);   //向下划分
    //归并
    memset(c+1,0,sizeof(int) * k);  //注意清空树状数组
    int pl(l),pr(mid+1);    //左右指针, 归并时使用
    int ctmp(l-1);
    for(;pr<=r;++pr) {
        trip& rt(atr[pr]);
        while(pl<=mid && atr[pl].y<=rt.y) {
            mdf(atr[pl].z,atr[pl].w);   //计入贡献
            tmp[++ctmp] = atr[pl++];    //归并排序
        }
        rt.ans += qry(rt.z);    //统计贡献
        tmp[++ctmp] = atr[pr];  //归并排序
    }
    while(pl<=mid) {    //左边剩余结点归并
        tmp[++ctmp] = atr[pl++];
    }
    memcpy(atr+l,tmp+l,sizeof(trip)*(r-l+1));
}

int main() {
    qrd(n), qrd(k);
    for(int i(1);i<=n;++i) {
        trip& nt(atr[i]);
        qrd(nt.x), qrd(nt.y), qrd(nt.z);
        nt.w = 1;
        nt.ans = 0;
    }
    sort(atr+1,atr+n+1);    //排序
    int cnt(1);
    for(int i(2);i<=n;++i) {    //去重
        trip& nt(atr[i]);
        if(nt==atr[cnt]) {
            ++atr[cnt].w;
        } else {
            atr[++cnt] = nt;
        }
    }
    cdq(1,cnt);
    for(int i(1);i<=cnt;++i) {
        trip& nt(atr[i]);
        ans[nt.ans+nt.w-1] += nt.w;
    }
    for(int i(0);i<n;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}