CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结,目前这个思想的拓展十分广泛。
- 优点:可以将数据结构或者 DP 优化掉一维
- 缺点:这是离线算法。
引入
让我们来看一个问题
有 $ n $ 个元素,第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性,设 $ f(i) $ 表示满足 $ a_j leq a_i $ 且 $ b_j leq b_i $ 且 $ c_j leq c_i $ 且 $ j ne i $ 的 (j) 的数量。
对于 $ d in [0, n) $,求 $ f(i) = d $ 的数量。
$ 1 leq n leq 10^5$,$1 leq a_i, b_i, c_i le k leq 2 times 10^5 $。
这是一个三维偏序问题。
偏序问题:给定序列 (A),其中有序对 ((A_i, A_j)),满足 (i 且 (A_i 这样的有序对我们称之为逆序对, 信息学竞赛中的逆序对问题,一般是要我们计数给出序列的逆序对个数的总和。其实可以把它看成一个特殊的二维偏序问题,或者说是离散化 (x) 坐标的二维偏序问题。
而 CDQ 分治,可以来解决三维偏序问题。
上面的引入问题就是模板题 P3810 【模板】三维偏序(陌上花开) 的题意。
P3810 【模板】三维偏序(陌上花开)
变量及其含义
struct node {
int x, y, z, cnt, ans;
} s1[N], s2[N];
x, y, z
: 三个元素。
cnt
:相同元素的个数。
ans
:统计答案。
对于第一维 (a),我们可以先从小到大 sort
一遍,(i) 号点前面的点的 (a) 都比 (a_i) 小,这样我们就减少了一维的处理,还剩下两维。
bool cmp1(node a, node b) {
if (a.x == b.x) {
if (a.y == b.y) {
return a.z (), k = read();
mx = k;
for (int i = 1, x, y, z; i (), y = read(), z = read();
s1[i].x = x, s1[i].y = y, s1[i].z = z;
}
sort(s1 + 1, s1 + n + 1, cmp1);
排完序后,我们可以将相同的元素合并为一个元素,结构体里的 cnt
就派上用场了。
int top = 0;
for (int i = 1; i
然后处理第二维,对于第二维,我们要求 (b_j leq b_i),按照前面的思路,我们肯定也要想方设法给第二维排序。
我们可以用 归并排序 的思想,先分别给左半个区间和右半个区间按照第二维从小到大排序,然后依次处理,由于是在 (a) 排好序的基础上进行的在排序,且这两个的区间还没有合并,所以无论怎么打乱,都可以保证左半边元素的 (a) 小于等于右半边元素的 (a)。
对于第三维,相当于到了我们找逆序对的环节了,我们有归并排序和树状数组两种方法,但由于归并排序已经放到前面去处理第二维了,所以我们用树状数组来处理第三维,将节点依次插入树状数组,统计。
bool cmp2(node a, node b) {
if (a.y == b.y) {
return a.z > 1;
cdq(l, mid);
cdq(mid + 1, r);
sort(s2 + l, s2 + mid + 1, cmp2);
sort(s2 + mid + 1, s2 + r + 1, cmp2);
int i, j = l;
for (i = mid + 1; i = s2[j].y && j
最后就是处理答案了,完整代码:
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include
using namespace std;
typedef long long ll;
#define lowbit(i) (i & (-i))
template
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch > 1;
cdq(l, mid);
cdq(mid + 1, r);
sort(s2 + l, s2 + mid + 1, cmp2);
sort(s2 + mid + 1, s2 + r + 1, cmp2);
int i, j = l;
for (i = mid + 1; i = s2[j].y && j (), k = read();
mx = k;
for (int i = 1, x, y, z; i (), y = read(), z = read();
s1[i].x = x, s1[i].y = y, s1[i].z = z;
}
sort(s1 + 1, s1 + n + 1, cmp1);
int top = 0;
for (int i = 1; i
P5094 [USACO04OPEN] MooFest G 加强版
一道比较好的入门题。统计答案的时候稍微麻烦一些。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include
using namespace std;
typedef long long ll;
template
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch > 1;
cdq(l, mid);
cdq(mid + 1, r);
sort(g + l, g + mid + 1, cmp2);
sort(g + mid + 1, g + r + 1, cmp2);
ll sum1 = 0, sum2 = 0;
for (int i = l; i ();
for (int i = 1; i (), x = read();
g[i] = node{v, x};
}
sort(g + 1, g + n + 1, cmp1);
cdq(1, n);
cout
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net