Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

学习笔记 CDQ分治 [CDQ分治]

Posted on Edited on In

CDQ分治可以代替一些高维的数据结构

例行 srO 陈丹琦

诶 今天是\(\pi\)日诶! QwQ

沙茶的 CDQ分治不详解

CDQ分治可以用来解决一些高维的偏序问题, 并可以适当的代替高维的数据结构

我认为 CDQ分治基本与普通的分治的最大区别就在于用左子区间的信息去修改维护右子区间的答案(就和归并排序一样, 或者说归并也是一种CDQ分治))

三维偏序

大体过程:

  1. 预处理, 将整个序列按照偏序的第一关键字排序
  2. 分, 将要处理的区间(询问和修改都有)[le, ri]分成[le, mi] + [mi + 1, ri], 然后递归, 直到le == ri, 返回
  3. 治, 将左右区间分别按照偏序的第二关键字排序, 就像归并排序一样, 一个指针dql扫描[le, mi], 一个指针i扫描[mi + 1, ri], 并时刻保证dql的第二关键字比i的第二关键字要小, 然后用数据结构(通常树状数组)维护第三关键字, 用左子区间的扫描更新右子区间的答案

复杂度\(n \lg^2 n\)

没了? 没了

非常优雅 非常好写

代码比口胡容易系列, 什么不懂的一看代码就懂...

四维偏序

没写过...坑...待填...

沙茶写过的 一些水题

保证难度递增

3262: 陌上花开

非常裸的三维偏序, 主要处理花相等的情况: 每次修改树状数组的时候不是加一而是加这个数出现的次数

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
 /**************************************************************
    Problem: 3262
    User: Cansult
    Language: C++
    Result: Accepted
    Time:3296 ms
    Memory:4752 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXZ (200000 + 5)
#define MAXN (100000 + 5)
#define lowbit(x) ((x) & (-(x)))
using namespace std;
struct flower
{
    int a, b, c, sum, cnt;
    /*bool operator != (const flower x)
    { return (a != x.a || b != x.b || c != x.c); }*/
    bool operator == (const flower x)
    { return a == x.a && b == x.b && c == x.c; }
    flower(): sum(0), cnt(0) {}
}a[MAXN];
int n, m, ans[MAXN], b[MAXZ];
bool cmpa(flower a, flower b)
{ return ((a.a != b.a) ? (a.a < b.a) : ((a.b == b.b) ? (a.c < b.c) : (a.b < b.b))); }
bool cmpb(flower a, flower b)
{ return ((a.b == b.b) ? (a.c < b.c) : (a.b < b.b)); }
void xg(int wz, int x)
{
    for (int i = wz; i <= m; i += lowbit(i))
        b[i] += x;
}
int cx(int wz)
{
    int re = 0;
    for (int i = wz; i; i -= lowbit(i))
        re += b[i];
    return re;
}
void cdq(int le, int ri)
{
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    cdq(le, mi), cdq(mi + 1, ri);
    sort(a + le, a + mi + 1, cmpb), sort(a + mi + 1, a + ri + 1, cmpb);
    /*printf("le: %d && ri: %d\n", le, ri);
    for (int i = le; i <= ri; i++)
        printf("%d\t", a[i].a);
    puts("");
    for (int i = le; i <= ri; i++)
        printf("%d\t", a[i].b);
    puts("");
    for (int i = le; i <= ri; i++)
        printf("%d\t", a[i].c);
    puts("");
    for (int i = le; i <= ri; i++)
        printf("%d\t", a[i].sum);*/
    int dql = le;
    for (int i = mi + 1; i <= ri; i++)
    {
        for (; dql <= mi && a[dql].b <= a[i].b; dql++)
            xg(a[dql].c, a[dql].cnt + 1);
        a[i].sum += cx(a[i].c);
    }
    /*puts("");
    for (int i = le; i <= ri; i++)
        printf("%d\t", a[i].sum);
    puts("\n--------------------------------------------\n");*/
    for (int i = le; i < dql; i++)
        xg(a[i].c, -a[i].cnt - 1);
}
int main()
{
 
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);
    sort(a + 1, a + n + 1, cmpa);
    int cnt[MAXN];
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i < n; i++)
    {
        if (a[i] == a[i + 1])
            cnt[i + 1] = cnt[i] + 1;
    }
    a[n].cnt = cnt[n];
    for (int i = n - 1; i >= 1; i--)
        if (a[i].c == a[i + 1].c && a[i].a == a[i + 1].a && a[i].b == a[i + 1].b)
            a[i].cnt =  a[i + 1].cnt;
        else
            a[i].cnt = cnt[i];
    int dn = n;
    n = unique(a + 1, a + n + 1) - a - 1;
    cdq(1, n);
    /*puts("\n");
    for (int i = 1; i <= n; i++)
        printf("%d %d %d: %d\n", a[i].a, a[i].b, a[i].c, a[i].sum);
    puts("\n");*/
    for (int i = 1; i <= n; i++)
        ans[a[i].sum + a[i].cnt] += a[i].cnt + 1;
    for (int i = 0; i < dn; i++)
        printf("%d\n", ans[i]);
    return 0;
}
 
/*
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
*/

1176: [Balkan2007]Mokia

依旧是个裸题, 把询问差分成四个前缀矩形即可

注意排序的时候还要按照其他关键字来排序_(:з」∠)_还要别把询问给当成修改给维护了...然后差分加一减一怎么现在还错啊QAQ还有别忘了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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**************************************************************
    Problem: 1176
    User: Cansult
    Language: C++
    Result: Accepted
    Time:13760 ms
    Memory:40360 kb
****************************************************************/
 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (2000000 + 5)
#define MAXQ (1000000 + 5)
#define lowbit(x) ((x) & (-(x)))
#define LL long long
using namespace std;
struct que
{
    int i, j, x;
    bool isC;
    int kind, belong, time;
    que() {}
    que(int dqi, int dqj, int dqx, bool change, int k, int bl, int tim): i(dqi), j(dqj), x(dqx), isC(change), kind(k), belong(bl), time(tim) {}
}q[MAXQ];
int b[MAXN], w, s, ans[MAXQ];
bool cmpa(que x, que y)
{ return (x.time == y.time ? ((x.i == y.i) ? (x.j < y.j) : (x.i < y.i)) : (x.time < y.time)); }
bool cmpb(que x, que y)
{ return ((x.i == y.i) ? (x.j < y.j) : (x.i < y.i)); }
void xg(int wz, int zh)
{
    for (int i = wz; i <= w; i += lowbit(i))
        b[i] += zh;
}
int cx(int wz)
{
    int re = 0;
    for (int i = wz; i; i -= lowbit(i))
        re += b[i];
    return re;
}
void cdq(int le, int ri)
{
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    cdq(le, mi), cdq(mi + 1, ri);
    sort(q + le, q + mi + 1, cmpb), sort(q + mi + 1, q + ri + 1, cmpb);
     
    /*
    printf("le: %d && ri: %d\n", le, ri);
    for (int i = le; i <= ri; i++)
        printf("%d\t", q[i].time);
    puts("");
    for (int i = le; i <= ri; i++)
        printf("%d\t", q[i].i);
    puts("");
    for (int i = le; i <= ri; i++)
        printf("%d\t", q[i].j);
    puts("");
    for (int i = le; i <= ri; i++)
        printf("%d\t", q[i].x);
    puts("");
    */
         
    int dql = le;
    for (int i = mi + 1; i <= ri; i++)
    {
        for (; dql <= mi && q[dql].i <= q[i].i; dql++)
            if (q[dql].isC)
                xg(q[dql].j, q[dql].x);
        if (!q[i].isC)
            q[i].x += cx(q[i].j);
    }
    /*
    for (int i = le; i <= ri; i++)
        printf("%d\t", q[i].x);
    puts("\n--------------------------------\n");
    */
    for (int i = le; i < dql; i++)
        if (q[i].isC)
            xg(q[i].j, -q[i].x);
}
int main()
{
     
    scanf("%d%d", &s, &w);
    int cntq = 0;
    queue<int> qq;
    for (int i = 1; ; i++)
    {
        int sre, srx, sry, srz;
        scanf("%d", &sre);
        if (sre == 3)
            break;
        scanf("%d%d%d", &srx, &sry, &srz);
        if (sre == 1)
            q[++cntq] = que(srx, sry, srz, true, 0, 0, i);
        else
        {
            scanf("%d", &sre);
            qq.push(i);
            q[++cntq] = que(srx - 1, sry - 1, 0, false, 1, i, i);
            q[++cntq] = que(srx - 1, sre, 0, false, -1, i, i);
            q[++cntq] = que(srz, sry - 1, 0, false, -1, i, i);
            q[++cntq] = que(srz, sre, 0, false, 1, i, i);
        }
    }
    sort(q + 1, q + cntq + 1, cmpa);
    cdq(1, cntq);
    for (int i = 1; i <= cntq; i++)
    {
        if (!q[i].isC)
            ans[q[i].belong] += q[i].x * q[i].kind;
    }
    while (!qq.empty())
    {
        printf("%d\n", ans[qq.front()] + s);
        qq.pop();
    }
    return 0;
}
 
/*
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
*/

2716: [Violet 3]天使玩偶

这题好神啊...参考了课件和CA爷爷的代码

只考虑左下角的加点对答案的影响, 如果在左下角加入一个点\((X, Y)\), 那么他对询问\((X_0, Y_0)\)的影响就是\(ans = min(ans, (X_0 - X) + (Y_0 - Y) = X_0 + Y_0 - (X + Y))\), 而 \(X_0 + Y_0\)已知, 那么问题就转化成找一个最大的\((X + Y) 满足 X < X_0, Y < Y_0\)看到这个...又是偏序, 又可以CDQ辣...

在找每一个修改的时候, 我们把它横坐标的位置\(B_i\)修改为\(max(B_i, X + Y)\), 然后查询的时候查询区间\((1, Y_0)\)的最大值即可(其他约束条件已经由分治去掉), 用树状数组维护一个最大值即可

然后考虑其他方向, 你可以用一个最大的坐标减去坐标来做, 具体看注释和代码

然后...你就可以卡常辣!

  1. 树状数组的清空不用memset而是遍历区间内包含的修改然后一个个置为0(好像全网就我一个傻不拉几的写的memset?)
  2. 每次返回上一层的时候用归并而非每一次都sort一遍, 实测快了3倍左右
  3. 读入优化 + inline + register + const + 手写带const的 max / min 而非define 大概快了100 ms+-
  4. 开小数组, 但注意bzoj的数据范围有问题, \(n, m\)的范围并非保证的 \(3 \times 10^5\) 而是 \(5\times10^5\) ...

还有一个小细节...坐标可以为0, 而树状数组下标不能为0...所以坐标在读入之前都应该加一, maxz也应该在最后加一防止计算新坐标的时候出现0坐标

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/**************************************************************
    Problem: 2716
    User: Cansult
    Language: C++
    Result: Accepted
    Time:67452 ms
    Memory:79420 kb
****************************************************************/
 
// luogu-judger-enable-o2
// CA Orz
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define pii pair<int, int>
#define MAXN (2000000 + 5)
#define MAXZ (2000000 + 5)
#define INF (0x7ffffff)
#define lowbit(x) ((x) & (-(x)))
using namespace std;
struct que
{
    int i, j, time;
    bool isC;
    que() {}
    que(int x, int y, int t, bool change): i(x), j(y), time(t), isC(change) {}
} a[MAXN], t[MAXN];
int b[MAXZ], n, m, maxz, ans[MAXN];
inline int mmax(const int a, const int b)
{
    if (a > b)   return a;
    else    return b;
}
inline int mmin(const int a, const int b)
{
    if (a > b)   return b;
    else    return a;
}
inline bool cmpa(que x, que y)
{
    return (x.time == y.time ? (x.i == y.i ? (x.j < y.j) : (x.i < y.i)) : (x.time < y.time));
}
inline bool cmpb(que x, que y)
{
    return (x.i == y.i ? (x.j < y.j) : (x.i < y.i));
}
// min(x0 - x + y0 - y) -> min(x0 + y0 - (x + y)) -> 维护三维偏序比当前节点小的(x + y)的最大值
// min(x0 - x + y - y0) -> min(x0 + size - y0 - (x + size - y))  -> 将所有y变成size - y, 得到新的三维值, 按照上面的做法搞一波就行了
// min(x - x0 + y - y0) -> min((size - x0) - (size - x) + (size - y0) - (size - y))
inline void qd(int wz)
{
    for (register int i = wz; i <= maxz; i += lowbit(i))
        b[i] = 0;
}
inline void xg(int wz, int zh)
{
    for (register int i = wz; i <= maxz; i += lowbit(i))
        b[i] = mmax(zh, b[i]);
}
inline int cx(int wz)
{
    int re = 0;
    for (register int i = wz; i; i -= lowbit(i))
        re = mmax(re, b[i]);
    return re;
}
void cdq(int le, int ri)
{
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    cdq(le, mi), cdq(mi + 1, ri);
    int dql = le;
    for (register int i = mi + 1; i <= ri; i++)
        if (!a[i].isC)
        {
            for (; dql <= mi && a[dql].i <= a[i].i; dql++)
                if (a[dql].isC)
                    xg(a[dql].j, a[dql].i + a[dql].j);
 
            int dqc = cx(a[i].j);
            if (dqc)
                ans[a[i].time] = mmin(ans[a[i].time], a[i].i + a[i].j - dqc);
        }
    for (register int i = le; i < dql; i++)
        if (a[i].isC)
            qd(a[i].j);
 
    int lx = le, rx = mi + 1, tx = le;
    for (; tx <= ri; tx++)
    {
        if (cmpb(a[lx], a[rx]))
            t[tx] = a[lx++];
        else
            t[tx] = a[rx++];
        if (lx > mi || rx > ri)
            break;
    }
    while (lx <= mi) t[++tx] = a[lx++];
    while (rx <= ri) t[++tx] = a[rx++];
    memcpy(a + le, t + le, (ri - le + 1) * sizeof(que));
}
inline int read()
{
    int re = 0;
    char x = 0;
    while (x < '0' || x > '9')
        x = getchar();
    while (x >= '0' && x <= '9')
    {
        re = (re << 1) + (re << 3) + x - '0';
        x = getchar();
    }
    return re;
}
int main()
{
    memset(ans, 0x7f, sizeof(ans));
    n = read(), m = read();
    int cntq = 0;
    for (int i = 1; i <= n; i++)
    {
        int srx, sry;
//      scanf("%d%d", &srx, &sry);
        srx = read(), sry = read();
        ++srx, ++sry;
        a[++cntq] = que(srx, sry, 0, true);
        maxz = mmax(maxz, mmax(srx, sry));
    }
    for (int i = 1; i <= m; i++)
    {
        int sre, srx, sry;
//      scanf("%d%d%d", &sre, &srx, &sry);
        sre = read(), srx = read(), sry = read();
        ++srx, ++sry;
        a[++cntq] = que(srx, sry, i, 2 - sre);
        maxz = mmax(maxz, mmax(srx, sry));
    }
    ++maxz;
    sort(a + 1, a + cntq + 1, cmpa);
    cdq(1, cntq);
    for (int i = 1; i <= cntq; i++)  a[i].i = maxz - a[i].i;
    sort(a + 1, a + cntq + 1, cmpa);
    cdq(1, cntq);
    for (int i = 1; i <= cntq; i++)  a[i].j = maxz - a[i].j;
    sort(a + 1, a + cntq + 1, cmpa);
    cdq(1, cntq);
    for (int i = 1; i <= cntq; i++)  a[i].i = maxz - a[i].i;
    sort(a + 1, a + cntq + 1, cmpa);
    cdq(1, cntq);
    sort(a + 1, a + cntq + 1, cmpa);
    for (int i = 1; i <= cntq; i++)
        if (!a[i].isC)
            printf("%d\n", ans[a[i].time]);
    return 0;
}
 
/*
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2
*/

By 四处蹭脸熟的 Cansult