Ntの咖啡馆
0%

浅谈cdq分治

发表于 更新于

前言

好像没啥可以说的。

本文主要介绍 cdq 分治在偏序问题上的应用。

正文

什么是 cdq 分治

分治，即字面意思，分而治之，cdq 分治是大佬 cdq 于高中结业时总结的一类分治模型，可以用来解决偏序，斜率优化等。

一维偏序

直接 sort 一遍就行了。

二维偏序

即逆序对，按照第一维排序，然后统计一下即可。

口胡几个算法。

写一棵平衡树，然后不断插入每个点，其贡献为 $i-kth(b_i)$。

写一棵主席树，离散化，然后不断插入每个点，贡献为 $i-ask(root_i,1,n,1,b_i)$。

三维偏序

每个 $i$ 都有三个值 $a_i,b_i,c_i$ 求 $\sum \limits_{i=1}^n \sum \limits_{j=1}^n [a_i \leq a_j \wedge b_i \leq b_j \wedge c_i \leq c_j]$。

考虑分治。首先把原数组按照第一维为关键字排序，这时候第一维就已经是有序的了，在对于第二维归并排序，比较第三位，把答案加到树状数组种即可，最后统计。

多维偏序

按照每一维归并，开 $n-3$（第一维和倒数第二维排好了，最后一维不用排）个数组记录前面的大小关系，写 $n-1$ 个归并，以及需要调很久的代码。

具体应用有三维偏序，四维偏序优化 LIS。

对于三维偏序，首先按照第一维排序，把第三维离散化（因为前面的二维只需要知道大小关系即可），再对第二维排序，计算对第三维的贡献。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void cdq(int l,int r) {
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(e+l,e+mid+1,cmp2);
    sort(e+mid+1,e+r+1,cmp2);
    int j=l;
    for (int i=mid+1;i<=r;i++) {
        while (j<=mid and e[j].b<=e[i].b) {
            upd(e[j].c,e[j].cnt);
            j++;
        }
        e[i].ans+=ask(e[i].c);
    }
    for (int i=l;i<j;i++) upd(e[i].c,-e[i].cnt);
}

对于四维偏序，和三维偏序差不多，首先对第一维排序，归并第二维（并不计算贡献），然后，对第二维排序，归并第三维，对第三维排序，计算贡献。

但是如果应用在 LIS 上的话，就不能按照左右中的顺序归并，因为对于 DP 它是一个递推的过程，而左边的对答案的贡献对右边对答案的贡献是有影响的，所以要左中右归并。

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
void cdq2(int l,int r) {
    if (l==r) return;
    int mid=(l+r>>1);
    cdq2(l,mid);
    sort(e+l,e+mid+1,cmp3); sort(e+mid+1,e+r+1,cmp3);
    int i=l,j=mid+1;
    while (i<=mid and j<=r) {
        if (e[i].v3<=e[j].v3) {
            if (!e[i].ok) upd(e[i].v4,e[i].ans);
            i++;
        } else {
            if (e[j].ok) e[j].ans=max(e[j].ans,ask(e[j].v4)+e[j].val);
            j++;
        }
    }
    while (i<=mid) { if (!e[i].ok) upd(e[i].v4,e[i].ans); i++; }
    while (j<=r) { if (e[j].ok) e[j].ans=max(e[j].ans,ask(e[j].v4)+e[j].val); j++;}
    for (int k=l;k<i;k++) if(!e[k].ok) clear(e[k].v4);
    for (int i=l;i<=r;i++) t[id2[e[i].id]]=e[i];
    for (int i=l;i<=r;i++) e[i]=t[i];
    cdq2(mid+1,r);
}

void cdq1(int l,int r) {
    if (l==r) return;
    int mid=(l+r>>1);
    cdq1(l,mid);
    for (int i=l;i<=mid;i++) e[i].ok=0;
    for (int i=mid+1;i<=r;i++) e[i].ok=1;
    sort(e+l,e+r+1,cmp2);
    for (int i=l;i<=r;i++) id2[e[i].id]=i;  
    cdq2(l,r);
    for (int i=l;i<=r;i++) t[id1[e[i].id]]=e[i];
    for (int i=l;i<=r;i++) e[i]=t[i];
    cdq1(mid+1,r);
}

咕咕咕