CDQ分治

CDQ分治

定义:

什么是CDQ分治呢。CDQ分治是雅礼的一名IOI金牌选手陈丹琦提出来的一种用分治的思想解决一类与维护决策有关的问题。现多用于求解偏序问题。

下面是她的原文:分治的基本思想是将一个规模为$N$的问题分解为$K$个规模较小的子问题,这些子问题互相独立且与原问题性质相同。求出子问题的接,就可得到原问题的接。分治算法非常基础,但是却非常重要,本文将从今年$NOI$的一道动态规划$Cash$开始谈如何利用分治思想来解决一类与维护决策有关的问题。(具体请看陈丹琦论文

主要思想:

用sort解决第一维,再用$N-2$层CDQ分治解决中间的$N-2$维,最后一维用树状数组实现。

你可能看到这还有一点不理解,我们以一下的题目为例,来具体讲解CDQ分治的用途以及如何实现。

二维偏序:

数星星

题面:lojpoj

二维的问题十分简单,因为$y$已经有序了所以我们可以考虑用树状数组来解决这题。我们可以维护一个树状数组按先后顺序依次插入元素,再查询当前的元素前面有多少个数。然后将答案存入一个数组,我们就可以写这题了。

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e4 + 10;
int n,ans[maxn],tree[maxn * 10];
struct node
{
int x;
int y;
}a[maxn];
void update(int x,int y)
{
for(int i = x ; i <= maxn * 2 ; i += (i & (-i)))
tree[i] += y;
}
int sum(int x)
{
int res = 0;
for(int i = x ; i ; i -= (i & (-i)))
res += tree[i];
return res;
}
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; ++ i)
cin >> a[i].x >> a[i].y;
for(int i = 1 ; i <= n ; ++ i)
{
int u = a[i].x + 1;
int v = sum(u);
update(u,1);
ans[v] ++;
}
for(int i = 0 ; i < n ; ++ i)
cout << ans[i] << endl;
return 0;
}

再看一题:

二维偏序模板题

这是一道简单的二维偏序题,我们仍然可以用树状数组简单的A掉这一题,注意的是我们在查询时因为$i_x <= j_x,i_y <= i_y$所以我们查询时我们需将查询的值加一在查询。但我们的目标不是用树状数组解决它,我们要用CDQ分治解决它。

就和基本解题思路一样,我们可以考虑先按照关键字$x$排序,然后因为$x$已经有序,所以我们只需要处理出满足$i_y <= j_y(i < j)$的顺序对个数就可以了(我们机房某神犇告诉我其实也可以用总共的对数也就是$n * (n - 1) / 2$减去逆序对个数来求解)

具体的代码:

顺序对:

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
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define int long long//注意一定要开long long不然只有30分
int n,cnt,t[maxn << 1],ans;
struct node
{
int x;int y;
}a[maxn];
bool cmp(node q,node p)
{
if(q.x != p.x)return q.x < p.x;
else return q.y < p.y;
}
void mergesort(int l,int r)
{
if(l == r)return;
int mid = l + r >> 1;
mergesort(l,mid);mergesort(mid + 1,r);
int p = l,q = mid + 1,cnt = l;
/* cout << "[" << l << "," << r << "]" << ": "<< endl;
for(int i = l ; i <= r ; ++ i)
cout << a[i].y << " ";
cout << endl << "ans: " << endl;*/
while(p <= mid and q <= r){
if(a[p].y <= a[q].y)t[cnt++] = a[p++].y,ans += r - q + 1;
else t[cnt++] = a[q++].y;
}
// cout << ans << endl;
while(p <= mid)t[cnt++] = a[p++].y;
while(q <= r)t[cnt++] = a[q++].y;
for(int i = l ; i <= r ; ++ i)a[i].y = t[i];
}
signed main()//相当与int main()
{
cin >> n;
for(int i = 1 ; i <= n ; ++ i)
cin >> a[i].x >> a[i].y;
sort(a + 1,a + n + 1,cmp);
/* for(int i = 1 ; i <= n ; ++ i)
cout << a[i].y << " ";
cout << endl;*/
mergesort(1,n);
cout << ans << endl;
return 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
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define int long long
int n,cnt,t[maxn << 1],ans;
struct node
{
int x;int y;
}a[maxn];
bool cmp(node q,node p)
{
if(q.x != p.x)return q.x < p.x;
else return q.y < p.y;
}
void mergesort(int l,int r)
{
if(l == r)return;
int mid = l + r >> 1;
mergesort(l,mid);mergesort(mid + 1,r);
int p = l,q = mid + 1,cnt = l;
while(p <= mid and q <= r){
if(a[p].y <= a[q].y)t[cnt++] = a[p++].y;
else{
t[cnt++] = a[q++].y;
ans += mid - p + 1;
}
}
while(p <= mid)t[cnt++] = a[p++].y;
while(q <= r)t[cnt++] = a[q++].y;
for(int i = l ; i <= r ; ++ i)a[i].y = t[i];
}
signed main()
{
cin >> n;
for(int i = 1 ; i <= n ; ++ i)
cin >> a[i].x >> a[i].y;
sort(a + 1,a + n + 1,cmp);
/*for(int i = 1 ; i <= n ; ++ i)
cout << a[i].y << " ";
cout << endl;*/
mergesort(1,n);
cout << n * (n - 1) / 2 - ans << endl;
return 0;
}

其中顺(逆)序对都是用归并排序实现的。

写了这么多,终于要步入正题了。

正题

由于本人太弱,目前只会三维的CDQ分治求解,高维要用CDQ套CDQ

三维偏序(陌上花开)

沿用二维偏序的代码和基本的解题思想,我们不难得出先sort出一维,再用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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n,k,ans[maxn],tree[maxn * 2];
struct flower
{
int x;int y;int z;int num;int ans;
}a[maxn],b[maxn];
bool cmp(flower &q,flower &p){
if(q.x != p.x)return q.x < p.x;
if(q.y != p.y)return q.y < p.y;
return q.z < p.z;
}
bool same(flower &q,flower &p)
{
return (q.x == p.x and q.y == p.y and q.z == p.z);
}
void add(int x,int y)
{
for(int i = x ; i <= k ; i += (i & (-i)))tree[i] += y;
return;
}
int query(int x){
int res = 0;
for(int i = x ; i ; i -= (i & (-i)))res += tree[i];
return res;
}
void cdq(int l,int r)
{
if(l >= r)return;
int mid = l + r >> 1;
cdq(l,mid);cdq(mid + 1,r);
for(int i = l,j = l,p = mid + 1;i <= r ; ++ i){
if(j <= mid and (p > r or a[j].y <= a[p].y))b[i] = a[j++];
else b[i] = a[p++];
}
for(int i = l ; i <= r ; ++ i){
a[i] = b[i];
if(a[i].num <= mid)add(a[i].z,1);
else a[i].ans += query(a[i].z);
}
for(int i = l ; i <= r ; ++ i)if(a[i].num <= mid)add(a[i].z,-1);
return;
}
int main()
{
cin >> n >> k;
for(int i = 1 ; i <= n ; ++ i)
cin >> a[i].x >> a[i].y >> a[i].z;
sort(a + 1,a + 1 + n,cmp);
flower t;int cnt = 1;
for(int i = n ; i >= 1 ; -- i){
if(same(t,a[i])){
a[i].ans += cnt;
++ cnt;
}
else {
t = a[i];
cnt = 1;
}
}
for(int i = 1 ; i <= n ; ++ i)a[i].num = i;
cdq(1,n);
for(int i = 1 ; i <= n ; ++ i)ans[a[i].ans]++;
for(int i = 0 ; i < n ; ++ i)cout << ans[i] << endl;
return 0;
}

终于写完了,呜呜呜呜~~数学立体几何好难啊,要是CDQ分治能解立体几何就好了。

同时以此文膜拜一下学姐。

各位晚安qwq。