CDQ分治学习笔记
发表更新ICPC/CCPC / Notes30 分钟读完 (大约4466个字)

CDQ分治学习笔记

参考博客：1 2 3 4 5

基本思想

分治(Divide and conquer)思想是计算机科学中举足轻重的一种思想，应用范围极为广泛。

CDQ 分治是普通分治思想的延伸，区别主要在于：普通分治的子问题之间互不影响，而 CDQ 分治中左子区间可以对右子区间有影响。

CDQ 分治应用广泛，在不同地方的体现不尽相同，实现上大体上可分为如下三步：

  • 分(Divide)：将原问题分为左右两个区间的子问题
  • 治(Conquer)：递归解决左右两个子区间
  • 并(Combine)：合并两子区间的答案，并且处理左区间对右区间产生的影响

可以发现，CDQ 分治的关键就在于如何处理左区间对右区间的影响，其余部分与普通分治相同。

CDQ 分治常常能够代替某些高级数据结构，并且常数更小，跑得更快。

练习

二维偏序（逆序对）

题目链接

逆序对问题本质就是一个二维偏序。CDQ 分治时，为了线性统计，我们希望左右子区间的数值已经排好序了，这样双指针就可以统计。所以归并排序正好用在了这里。

复杂度：$T(n)=2\cdot T\left(\frac{n}{2}\right)+O(n)=O(n\lg n)$

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 500005;

int n, a[N];
LL ans;

int t[N];
void cdq(int l, int r){
    if(l == r)	return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid+1, r);
    t[0] = 0;
    int lpt = l, rpt = mid+1;
    while(lpt <= mid && rpt <= r){
        if(a[lpt] <= a[rpt])    t[++t[0]] = a[lpt++];
        else    t[++t[0]] = a[rpt++], ans += mid - lpt + 1;
    }
    while(lpt <= mid)   t[++t[0]] = a[lpt++];
    while(rpt <= r) t[++t[0]] = a[rpt++];
    for(int i = l; i <= r; i++) a[i] = t[i - l + 1];
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    cdq(1, n);
    printf("%lld\n", ans);
    return 0;
}

hdu1541 Stars

题目链接

求横纵坐标都更小的点的个数，二维偏序。

>folded
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
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 1000005;

int n, ans[N];

struct Node{
    int x, y, id;
    int cnt;
}node[N];
bool cmpx(const Node &A, const Node &B){
    return A.x == B.x ? A.y < B.y : A.x < B.x;
}

int t[N];
void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= n; i++)
        node[i].y = lower_bound(t+1, t+t[0]+1, node[i].y) - t;
}

Node tmp[N];
void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid+1, r);
    int posl = l, posr = mid+1, tid = 0;
    while(posl <= mid && posr <= r){
        if(node[posl].y <= node[posr].y)    tmp[++tid] = node[posl++];
        else{
            node[posr].cnt += posl - l;
            tmp[++tid] = node[posr++];
        }
    }
    while(posl <= mid)  tmp[++tid] = node[posl++];
    while(posr <= r)    node[posr].cnt += posl - l, tmp[++tid] = node[posr++];
    for(int i = 1; i <= tid; i++)   node[i+l-1] = tmp[i];
}

int main(){
    while(scanf("%d", &n) != EOF){
        t[0] = 0;
        memset(ans, 0, sizeof ans);
        for(int i = 1; i <= n; i++){
            scanf("%d%d", &node[i].x, &node[i].y);
            t[++t[0]] = node[i].y;
            node[i].id = i;
            node[i].cnt = 0;
        }
        disc();
        sort(node+1, node+n+1, cmpx);
        cdq(1, n);
        for(int i = 1; i <= n; i++) ans[node[i].cnt]++;
        for(int i = 0; i < n; i++)  printf("%d\n", ans[i]);
    }
    return 0;
}

[SHOI2007]园丁的烦恼

题目链接

用二维前缀和转化一下，然后就是求横纵坐标都更小的点的个数，即二维偏序问题。

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

const int N = 500005;

int n, m, tot, a[N], b[N], c[N], d[N], ans[N], maxx;

struct Node{
    int x, y, k, id;
}node[N*5];
bool cmp1(const Node &A, const Node &B){
    return A.x == B.x ? (A.y == B.y ? A.k == 0 : A.y < B.y) : A.x < B.x;
}

int t[N*5];
void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= tot; i++){
        node[i].y = lower_bound(t+1, t+t[0]+1, node[i].y) - t;
        maxx = max(maxx, node[i].y);
    }
}

Node tmp[N*5];
void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid+1, r);
    int posl = l, posr = mid+1, tid = 0, res = 0;
    while(posl <= mid && posr <= r){
        if(node[posl].y <= node[posr].y){
            res += (node[posl].k == 0);
            tmp[++tid] = node[posl++];
        }
        else{
            ans[node[posr].id] += node[posr].k * res;
            tmp[++tid] = node[posr++];
        }
    }
    while(posl <= mid)  tmp[++tid] = node[posl++];
    while(posr <= r)    ans[node[posr].id] += node[posr].k * res, tmp[++tid] = node[posr++];
    for(int i = 1; i <= tid; i++)   node[i+l-1] = tmp[i];
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &node[i].x, &node[i].y);
        tot++;
        t[++t[0]] = node[i].y;
    }
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
        t[++t[0]] = b[i]-1, t[++t[0]] = d[i];
        node[++tot] = (Node){a[i]-1, b[i]-1, 1, i};
        node[++tot] = (Node){a[i]-1, d[i], -1, i};
        node[++tot] = (Node){c[i], b[i]-1, -1, i};
        node[++tot] = (Node){c[i], d[i], 1, i};
    }
    disc();
    sort(node+1, node+tot+1, cmp1);
    cdq(1, tot);
    for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

luoguP2345 奶牛集会

题目链接

先把所有奶牛按照 $v$ 排序，然后 CDQ 分治。在考虑左右子区间时，左子区间的任一 $v$ 都小于右子区间的任一 $v$，于是我们只需要依次考虑右子区间的每一个元素，计算左子区间中 $x$ 比它小的坐标之和以及 $x$ 比它大的坐标之和是多少。欲在这一步做到线性，我们希望左右区间分别是按照 $x$ 排好序了的，这样就可以用双指针的方法搞出答案。正好把归并排序套上去即可。

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 20005;

int n;
LL ans;

struct Node{
    LL v, x;
}node[N];
bool cmp1(const Node &A, const Node &B){ return A.v == B.v ? A.x < B.x : A.v < B.v; }

Node tmp[N];
void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid+1, r);
    LL sumb = 0, sums = 0;
    int pt = l;
    for(int i = l; i <= mid; i++)   sumb += node[i].x;
    for(int i = mid + 1; i <= r; i++){
        while(node[i].x > node[pt].x && pt <= mid){
            sumb -= node[pt].x;
            sums += node[pt].x;
            pt++;
        }
        ans += node[i].v * (sumb - node[i].x * (mid + 1 - pt) + node[i].x * (pt - l) - sums);
    }
    int ptl = l, ptr = mid + 1, tid = 0;
    while(ptl <= mid && ptr <= r){
        if(node[ptl].x < node[ptr].x)   tmp[++tid] = node[ptl++];
        else    tmp[++tid] = node[ptr++];
    }
    while(ptl <= mid)   tmp[++tid] = node[ptl++];
    while(ptr <= r) tmp[++tid] = node[ptr++];
    for(int i = 1; i <= tid; i++)   node[i+l-1] = tmp[i];
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld%lld", &node[i].v, &node[i].x);
    sort(node+1, node+n+1, cmp1);
    cdq(1, n);
    printf("%lld\n", ans);
    return 0;
}

三维偏序（陌上花开）

题目链接

先按第一维排序，然后 CDQ 分治：solve(l, r) 时，递归进行 solve(l, mid) 和 solve(mid+1, r)，考虑如何统计 $l\leq i\leq mid,mid+1\leq j\leq r$ 的满足 $b_i<b_j$ 且 $c_i<c_j$ 的点对数。把所有 $[l,r]$ 区间的元素拿出来按第二维排序，遍历一遍，遇到左区间的就按第三维丢到值域树状数组里去，遇到右区间的就查询。

如果题目存在重复元素，需要去重（因为 CDQ 分治只能统计左区间对右区间的答案），丢值域树状数组的时候丢重复次数。

复杂度：$T(n)=2\cdot T\left(\frac{n}{2}\right)+O(n\lg n)=O(n\lg^2n)$

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

const int N = 100005;
const int K = 200005;

int n, k, tot, ans[N], ranking[N]; // ranking[i] is the number less than ith element
struct Node{
    int a, b, c, dc;    // dc is c after discretization
    int newid, cnt, num; // num is the number of elements which are less than this node
}node[N];
bool cmpa(const Node &A, const Node &B){
    return A.a == B.a ? (A.b == B.b ? A.c < B.c : A.b < B.b) : A.a < B.a;
}
bool cmpb(const Node &A, const Node &B){
    return A.b == B.b ? (A.c == B.c ? A.a < B.a : A.c < B.c) : A.b < B.b;
}

int tc[N];
void disc(){
    sort(tc+1, tc+tc[0]+1);
    tc[0] = unique(tc+1, tc+tc[0]+1) - (tc+1);
    for(int i = 1; i <= n; i++)
        node[i].dc = lower_bound(tc+1, tc+tc[0]+1, node[i].c) - tc;
}

int c[N];
inline int lowbit(int x){ return x & -x; }
void add(int x, int val){ while(x <= n){ c[x] += val; x += lowbit(x); } }
int sum(int x){
    int res = 0;
    while(x){ res += c[x]; x -= lowbit(x); }
    return res;
}

void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid+1, r);
    sort(node+l, node+r+1, cmpb);
    for(int i = l; i <= r; i++){
        if(node[i].newid <= mid)    add(node[i].dc, node[i].cnt);
        else    node[i].num += sum(node[i].dc);
    }
    for(int i = l; i <= r; i++)         // clear BIT
        if(node[i].newid <= mid)
            add(node[i].dc, -node[i].cnt);
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &node[i].a, &node[i].b, &node[i].c);
        tc[++tc[0]] = node[i].c;
    }
    disc();
    sort(node+1, node+n+1, cmpa);
    for(int i = 1; i <= n; i++){ // unique
        if(node[i-1].a != node[i].a || node[i-1].b != node[i].b || node[i-1].c != node[i].c)
            node[++tot] = node[i], node[tot].newid = tot, node[tot].cnt = 1;
        else    node[tot].cnt++;
    }
    cdq(1, tot);
    for(int i = 1; i <= tot; i++)   ans[node[i].num + node[i].cnt - 1] += node[i].cnt;
    for(int i = 0; i < n; i++)  printf("%d\n", ans[i]);
    return 0;
}

动态逆序对

题目链接

删去一个值后，总逆序对数等于原逆序对数减去它参与构成的逆序对数。它参与构成的逆序对分两种情况：

  • 位置在其前，值更大，删去时间更大
  • 位置在其后，值更小，删去时间更大

这分别是两种三维偏序，CDQ 分治即可。

>folded
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
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 200005;

typedef long long LL;

int n, m, pos[N];
struct Query{
    int tim, pos, val;
    int newid, num;
}node[N];
bool cmp1(const Query &A, const Query &B){ return A.tim > B.tim; }
bool cmp2(const Query &A, const Query &B){ return A.pos > B.pos; }

int c[N];
inline int lowbit(int x){ return x & -x; }
void add(int x, int val){ while(x <= n+1){ c[x] += val; x += lowbit(x); } }
int sum(int x){
    int res = 0;
    while(x){ res += c[x]; x -= lowbit(x); }
    return res;
}

void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid+1, r);
    sort(node+l, node+r+1, cmp2);
    for(int i = l; i <= r; i++){
        if(node[i].newid <= mid)    add(node[i].val, 1);
        else    node[i].num += sum(node[i].val);
    }
    for(int i = l; i <= r; i++)
        if(node[i].newid <= mid)
            add(node[i].val, -1);
    for(int i = r; i >= l; i--){
        if(node[i].newid <= mid)    add(n + 1 - node[i].val, 1);
        else    node[i].num += sum(n + 1 - node[i].val);
    }
    for(int i = r; i >= l; i--)
        if(node[i].newid <= mid)
            add(n + 1 - node[i].val, -1);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &node[i].val);
        pos[node[i].val] = i;
        node[i].pos = i;
    }
    for(int i = 1; i <= m; i++){
        int x; scanf("%d", &x);
        node[pos[x]].tim = i;
    }
    for(int i = 1; i <= n; i++)
        if(!node[i].tim)
            node[i].tim = m + 1;
    LL res = 0;
    for(int i = n; i >= 1; i--)
        res += sum(node[i].val - 1), add(node[i].val, 1);
    for(int i = n; i >= 1; i--) add(node[i].val, -1);
    sort(node+1, node+n+1, cmp1);
    for(int i = 1; i <= n; i++) node[i].newid = i;
    cdq(1, n);
    sort(node+1, node+n+1, cmp1);
    for(int i = n; i >= n - m + 1; i--){
        printf("%lld\n", res);
        res -= node[i].num;
    }
    return 0;
}

[BOI2007]Mokia

题目链接

求横纵坐标以及时间都更小的点的数目，三维偏序。

以下代码中的排序采用了另一种方式（分别排序），两种都可以，看心情用咯～

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 800005;

int n, tot, opt[N];

struct Node{
    int x, y, t, k;
    LL val;
}node[N];
bool cmpt(const Node &A, const Node &B){
    return A.t == B.t ? (A.x == B.x ? A.y < B.y : A.x < B.x) : A.t < B.t;
}
bool cmpx(const Node &A, const Node &B){
    return A.x == B.x ? (A.y == B.y ? A.t < B.t : A.y < B.y) : A.x < B.x;
}

int t[N];
inline void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= tot; i++)
        node[i].y = lower_bound(t+1, t+t[0]+1, node[i].y) - t;
}

LL c[N];
inline int lowbit(int x){ return x & -x; }
inline void add(int x, LL val){ while(x <= tot){ c[x] += val; x += lowbit(x); } }
inline LL sum(int x){ LL res = 0; while(x){ res += c[x]; x -= lowbit(x); } return res; }

LL ans[N];
void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid+1, r);
    sort(node+l, node+mid+1, cmpx);
    sort(node+mid+1, node+r+1, cmpx);
    int ptl = l, ptr;
    for(ptr = mid+1; ptr <= r; ptr++){
        while(ptl <= mid && node[ptl].x <= node[ptr].x){
            if(node[ptl].k == 0)    add(node[ptl].y, node[ptl].val);
            ptl++;
        }
        ans[node[ptr].t] += node[ptr].k * sum(node[ptr].y);
    }
    for(int i = l; i < ptl; i++) if(node[i].k == 0) add(node[i].y, -node[i].val);
}

int main(){
    scanf("0 %d", &n);
    for(int i = 1; ; i++){
        scanf("%d", &opt[++opt[0]]);
        if(opt[i] == 3)    break;
        else if(opt[i] == 1){
            int x, y; LL A; scanf("%d%d%lld", &x, &y, &A);
            ++tot, node[tot] = (Node){x, y, i, 0, A};
            t[++t[0]] = y;
        }
        else if(opt[i] == 2){
            int _x1, _y1, _x2, _y2;
            scanf("%d%d%d%d", &_x1, &_y1, &_x2, &_y2);
            tot++, node[tot] = (Node){_x2, _y2, i, 1, 0};
            tot++, node[tot] = (Node){_x1-1, _y2, i, -1, 0};
            tot++, node[tot] = (Node){_x2, _y1-1, i, -1, 0};
            tot++, node[tot] = (Node){_x1-1, _y1-1, i, 1, 0};
            t[++t[0]] = _y2, t[++t[0]] = _y1-1;
        }
    }
    disc();
    sort(node+1, node+tot+1, cmpt);
    cdq(1, tot);
    for(int i = 1; i <= opt[0]; i++)
        if(opt[i] == 2)
            printf("%lld\n", ans[i]);
    return 0;
}

luoguP4169 [Violet]天使玩偶/SJY摆棋子

题目链接

正解是 K-D Tree，但是也可以用 CDQ 分治做。考虑如何把最近距离问题转换成三维偏序问题——每个点的左下、左上、右下、右上部分分别求最近距离，这样就是四次三维偏序问题。为方便写代码，左上、右下、右上可以通过翻转转化成左下。

这道题时限很紧，在 CDQ 分治中不采用 sort 来排序第二维，而是套用一个归并排序，可以减少不少常数，然后提交的时候吸吸氧就可以过了。

>folded
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
#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
            fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

const int N = 1000005;
const int INF = 2e9;

int n, m, tot, ans[N], maxx, maxdy, maxy, _[N];
struct Node{
    int t, x, y, k, id, dy;
}node[N], nod[N];
bool cmpt(const Node &A, const Node &B){ return A.t == B.t ? (A.x == B.x ? A.y < B.y : A.x < B.x) : A.t < B.t; }

int t[N];
void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= tot; i++){
        node[i].dy = lower_bound(t+1, t+t[0]+1, node[i].y) - t;
        maxdy = max(maxdy, node[i].dy);
        maxy = max(maxy, node[i].y);
        maxx = max(maxx, node[i].x);
    }
}

int c[N];
inline int lowbit(int x){ return x & -x; }
inline void modify(int x, int val){ while(x <= n + m + 1){ c[x] = max(c[x], val); x += lowbit(x); } }
inline int queryMax(int x){ int res = -1e9; while(x){ res = max(res, c[x]); x -= lowbit(x); } return res; }
inline void clear(int x){ while(x <= n + m + 1){ c[x] = 0; x += lowbit(x); } }

Node tmp[N];
void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid+1, r);
    int ptl = l, tid = 0;
    for(int ptr = mid+1; ptr <= r; ptr++){
        while(ptl <= mid && node[ptl].x <= node[ptr].x){
            if(node[ptl].k) modify(node[ptl].dy, node[ptl].x + node[ptl].y);
            tmp[++tid] = node[ptl++];
        }
        if(node[ptr].id){
            int res = queryMax(node[ptr].dy);
            if(res) ans[node[ptr].id] = min(ans[node[ptr].id], node[ptr].x + node[ptr].y - queryMax(node[ptr].dy));
        }
        tmp[++tid] = node[ptr];
    }
    for(int i = l; i < ptl; i++)    clear(node[i].dy);
    while(ptl <= mid)   tmp[++tid] = node[ptl++];
    for(int i = 1; i <= tid; i++)   node[i+l-1] = tmp[i];
}

int main(){
    read(n, m);
    for(int i = 1; i <= n; i++){
        read(node[i].x, node[i].y);
        node[i].t = 0, node[i].k = 1;
        tot++;
        t[++t[0]] = node[i].y;
    }
    for(int i = 1; i <= m; i++){
        tot++;
        read(_[i], node[tot].x, node[tot].y);
        node[tot].t = i, node[tot].k = (_[i] == 1), node[tot].id = (_[i] == 2) * i;
        t[++t[0]] = node[tot].y;
        ans[i] = INF;
    }
    disc();
    sort(node+1, node+tot, cmpt);
    for(int i = 1; i <= tot; i++)   nod[i] = node[i];
    cdq(1, tot);
    for(int i = 1; i <= tot; i++)
        node[i] = nod[i], node[i].y = maxy - nod[i].y + 1, node[i].dy = maxdy - nod[i].dy + 1;
    cdq(1, tot);
    for(int i = 1; i <= tot; i++)
        node[i] = nod[i], node[i].x = maxx - nod[i].x + 1;
    cdq(1, tot);
    for(int i = 1; i <= tot; i++)
        node[i] = nod[i], node[i].x = maxx - nod[i].x + 1, node[i].y = maxy - nod[i].y + 1, node[i].dy = maxdy - nod[i].dy + 1;
    cdq(1, tot);
    for(int i = 1; i <= m; i++)
        if(_[i] == 2)
            printf("%d\n", ans[i]);
    return 0;
}

四维偏序（hdu5126 stars）

题目链接

CDQ 套 CDQ分治。先按第一维 $a$ 排序，然后对第一维 CDQ 分治：递归回来后根据第一维的位置打上左右标记，然后按 $b$ 排序，得到一系列形如 $(L/R,b,c,d)$ 的元素且 $b$ 递增；复制一下，对第二维 CDQ 分治并在同时对第三维排序：递归回来后左子区间都是 $(L/R,L,c,d)$，右子区间都是 $(L/R,R,c,d)$，且各自区间内的 $c$ 是递增的，然后双指针把第四维丢值域树状数组里或者查询，丢的时候记得参考第一维的 $L/R$ 情况。

实现时用与 CDQ 浑然一体的归并排序而非 sort 来减少一些常数；同时清空树状数组时尽可能少清。

复杂度：$T(n)=2\cdot T\left(\frac{n}{2}\right)+O(n\lg^2n)=O(n\lg^3n)$

>folded
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
117
118
119
120
121
122
123
124
125
126
127
#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

const int N = 50005;

int T, q, a[N], tot, ans[N];

#define LEFT 0
#define RIGHT 1
struct Node{
    int t, x, y, z, k;
    bool mark;
}node[N<<3];
bool cmpt(const Node &A, const Node &B){
    if(A.t == B.t) if(A.x == B.x) if(A.y == B.y) return A.z < B.z;
    else return A.y < B.y; else return A.x < B.x; else return A.t < B.t;
}

int t[N<<3];
void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= tot; i++)
        node[i].z = lower_bound(t+1, t+t[0]+1, node[i].z) - t;
}

int c[N<<3];
inline int lowbit(int x){ return x & -x; }
inline void add(int x, int val){ while(x <= q * 8){ c[x] += val; x += lowbit(x); } }
inline int sum(int x){ int res = 0; while(x){ res += c[x]; x -= lowbit(x); } return res; }

Node tmp[N<<3], tmp2[N<<3];
void cdq2(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq2(l, mid), cdq2(mid+1, r);
    int ptl = l, ptr = mid+1, tid = l-1, lastl;
    while(ptl <= mid && ptr <= r){
        if(tmp[ptl].y <= tmp[ptr].y){
            if(tmp[ptl].k == 0 && tmp[ptl].mark == LEFT)
                add(tmp[ptl].z, 1);
            tmp2[++tid] = tmp[ptl++];
        }
        else{
            if(tmp[ptr].k != 0 && tmp[ptr].mark == RIGHT)
                ans[tmp[ptr].t] += tmp[ptr].k * sum(tmp[ptr].z);
            tmp2[++tid] = tmp[ptr++];
        }
    }
    lastl = ptl - 1;
    while(ptl <= mid)   tmp2[++tid] = tmp[ptl++];
    while(ptr <= r){
        if(tmp[ptr].k != 0 && tmp[ptr].mark == RIGHT)
            ans[tmp[ptr].t] += tmp[ptr].k * sum(tmp[ptr].z);
        tmp2[++tid] = tmp[ptr++];
    }
    for(int i = l; i <= lastl; i++) // crucial for decreasing constant
        if(tmp[i].k == 0 && tmp[i].mark == LEFT)
            add(tmp[i].z, -1);
    for(int i = l; i <= r; i++) tmp[i] = tmp2[i];
}
void cdq1(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq1(l, mid), cdq1(mid+1, r);
    int ptl = l, ptr = mid+1, tid = l-1; // tid must be l-1 or it can't be used in cdq2
    while(ptl <= mid && ptr <= r){
        if(node[ptl].x <= node[ptr].x){
            node[ptl].mark = LEFT;
            tmp[++tid] = node[ptl++];
        }
        else{
            node[ptr].mark = RIGHT;
            tmp[++tid] = node[ptr++];
        }
    }
    while(ptl <= mid)   node[ptl].mark = LEFT, tmp[++tid] = node[ptl++];
    while(ptr <= r)     node[ptr].mark = RIGHT, tmp[++tid] = node[ptr++];
    for(int i = l; i <= r; i++)   node[i] = tmp[i];
    cdq2(l, r);
}

inline void init(){
    tot = t[0] = 0;
    for(int i = 1; i <= q; i++) ans[i] = 0;
}

int main(){
    read(T);
    while(T--){
        read(q);
        init();
        int _x1, _y1, _z1, _x2, _y2, _z2;
        for(int i = 1; i <= q; i++){
            read(a[i], _x1, _y1, _z1);
            if(a[i] == 1){
                node[++tot] = (Node){i, _x1, _y1, _z1, 0};
                t[++t[0]] = _z1;
            }
            else{
                read(_x2, _y2, _z2);
                node[++tot] = (Node){i, _x2, _y2, _z2, 1};
                node[++tot] = (Node){i, _x1-1, _y2, _z2, -1};
                node[++tot] = (Node){i, _x2, _y1-1, _z2, -1};
                node[++tot] = (Node){i, _x2, _y2, _z1-1, -1};
                node[++tot] = (Node){i, _x1-1, _y1-1, _z2, 1};
                node[++tot] = (Node){i, _x1-1, _y2, _z1-1, 1};
                node[++tot] = (Node){i, _x2, _y1-1, _z1-1, 1};
                node[++tot] = (Node){i, _x1-1, _y1-1, _z1-1, -1};
                t[++t[0]] = _z2, t[++t[0]] = _z1-1;
            }
        }
        disc();
        sort(node+1, node+tot+1, cmpt);
        cdq1(1, tot);
        for(int i = 1; i <= q; i++)
            if(a[i] == 2)
                printf("%d\n", ans[i]);
    }
    return 0;
}

CDQ分治学习笔记

http://xyfjason.github.io/blog-xcpc/2020/02/19/CDQ分治学习笔记/

作者

xyfJASON

发布于

2020-02-19

更新于

2021-02-25

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×