CDQ分治算法详解与应用
基础概念
CDQ分治是一种解决多维偏序问题的经典算法，通过分治思想将高维问题降维处理。
BZOJ1935 园丁的烦恼
解题思路
将二维平面查询转化为四个前缀和的组合。设置时间、横坐标、纵坐标三个维度，采用时间分治、横坐标归并、纵坐标使用树状数组维护。
实现代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500007;
const int MAXM = 10000007;
struct Query {
int type, x, y, coeff, index;
} items[MAXN * 5];
int n, q, total;
int result[MAXN], fenwick[MAXM];
void update(int pos, int delta) {
while(pos < MAXM) {
fenwick[pos] += delta;
pos += pos & (-pos);
}
}
int query(int pos) {
int sum = 0;
while(pos) {
sum += fenwick[pos];
pos -= pos & (-pos);
}
return sum;
}
bool compare(Query a, Query b) {
return a.x == b.x ? a.y < b.y : a.x < a.x;
}
void solveCDQ(int left, int right) {
if(left == right) return;
int mid = (left + right) >> 1;
solveCDQ(left, mid);
solveCDQ(mid + 1, right);
int i = left;
for(int j = mid + 1; j <= right; ++j) {
if(items[j].type == 2) {
for(; i <= mid && items[i].x <= items[j].x; ++i) {
if(items[i].type == 1)
update(items[i].y, items[i].coeff);
}
result[items[j].index] += items[j].coeff * query(items[j].y);
}
}
--i;
while(i >= left) {
if(items[i].type == 1) update(items[i].y, -1);
--i;
}
inplace_merge(items + left, items + mid + 1, items + right + 1, compare);
}
int main() {
scanf("%d%d", &n, &q);
// 添加点
for(int i = 1; i <= n; ++i) {
int x, y;
scanf("%d%d", &x, &y);
items[++total] = {1, x + 1, y + 1, 1, 0};
}
// 处理查询
for(int i = 1; i <= q; ++i) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x1++, y1++, x2++, y2++;
items[++total] = {2, x2, y2, 1, i};
items[++total] = {2, x1 - 1, y2, -1, i};
items[++total] = {2, x2, y1 - 1, -1, i};
items[++total] = {2, x1 - 1, y1 - 1, 1, i};
}
solveCDQ(1, total);
for(int i = 1; i <= q; ++i)
printf("%d\n", result[i]);
return 0;
}
BZOJ1176 Mokia
解题思路
支持动态插入点的二维查询问题。处理方法与上题类似，但需要处理动态加点操作。
实现代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000007;
int width, count_ops, query_id;
int tree[MAXN], answers[MAXN];
struct Element {
int x, y, operation, value, id;
bool operator < (const Element& other) const {
return x == other.x ? y < other.y : x < x;
}
} elements[MAXN];
void modify(int pos, int delta) {
while(pos <= width) {
tree[pos] += delta;
pos += pos & (-pos);
}
}
int sum_query(int pos) {
int res = 0;
while(pos) {
res += tree[pos];
pos -= pos & (-pos);
}
return res;
}
void divide_conquer(int left, int right) {
if(left == right) return;
int mid = (left + right) >> 1;
divide_conquer(left, mid);
divide_conquer(mid + 1, right);
int i = left;
for(int j = mid + 1; j <= right; ++j) {
if(elements[j].operation == 2) {
for(; i <= mid && elements[i].x <= elements[j].x; ++i) {
if(elements[i].operation == 1)
modify(elements[i].y, elements[i].value);
}
answers[elements[j].id] += elements[j].value * sum_query(elements[j].y);
}
}
--i;
while(i >= left) {
if(elements[i].operation == 1)
modify(elements[i].y, -elements[i].value);
--i;
}
inplace_merge(elements + left, elements + mid + 1, elements + right + 1);
}
int main() {
scanf("%*d%d", &width);
int op;
while(scanf("%d", &op) && op != 3) {
if(op == 1) {
int x, y, val;
scanf("%d%d%d", &x, &y, &val);
elements[++count_ops] = {x, y, 1, val, 0};
} else {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
++query_id;
elements[++count_ops] = {x1 - 1, y1 - 1, 2, 1, query_id};
elements[++count_ops] = {x1 - 1, y2, 2, -1, query_id};
elements[++count_ops] = {x2, y1 - 1, 2, -1, query_id};
elements[++count_ops] = {x2, y2, 2, 1, query_id};
}
}
divide_conquer(1, count_ops);
for(int i = 1; i <= query_id; ++i)
printf("%d\n", answers[i]);
return 0;
}
陌上花开
解题思路
经典的三维偏序问题。在进行CDQ分治前需合并相同元素，分治第一维，归并第二维，树状数组维护第三维。
实现代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200007;
struct Flower {
int a, b, c, count, level;
} temp[MAXN], flowers[MAXN];
int n, k, total;
int bit[MAXN], rank_count[MAXN];
bool cmp_a(Flower x, Flower y) {
return x.a != y.a ? x.a < y.a :
x.b != y.b ? x.b < y.b : x.c < y.c;
}
bool cmp_b(Flower x, Flower y) {
return x.b != y.b ? x.b < y.b : x.c < y.c;
}
void add_bit(int pos, int delta) {
while(pos <= k) {
bit[pos] += delta;
pos += pos & (-pos);
}
}
int query_bit(int pos) {
int res = 0;
while(pos) {
res += bit[pos];
pos -= pos & (-pos);
}
return res;
}
void cdq_solve(int left, int right) {
if(left == right) return;
int mid = (left + right) >> 1;
cdq_solve(left, mid);
cdq_solve(mid + 1, right);
int i = left, j = mid + 1;
while(i <= mid && j <= right) {
if(flowers[i].b <= flowers[j].b) {
add_bit(flowers[i].c, flowers[i].count);
++i;
} else {
flowers[j].level += query_bit(flowers[j].c);
++j;
}
}
while(j <= right) {
flowers[j].level += query_bit(flowers[j].c);
++j;
}
--i;
while(i >= left) {
add_bit(flowers[i].c, -flowers[i].count);
--i;
}
inplace_merge(flowers + left, flowers + mid + 1, flowers + right + 1, cmp_b);
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%d%d%d", &temp[i].a, &temp[i].b, &temp[i].c);
}
sort(temp + 1, temp + n + 1, cmp_a);
flowers[++total] = temp[1];
flowers[total].count = 1;
flowers[total].level = 0;
for(int i = 2; i <= n; ++i) {
if(temp[i].a == flowers[total].a &&
temp[i].b == flowers[total].b &&
temp[i].c == flowers[total].c) {
++flowers[total].count;
flowers[total].level = 0;
} else {
flowers[++total] = temp[i];
flowers[total].count = 1;
flowers[total].level = 0;
}
}
cdq_solve(1, total);
for(int i = 1; i <= total; ++i) {
rank_count[flowers[i].count - 1 + flowers[i].level] += flowers[i].count;
}
for(int i = 0; i < n; ++i) {
printf("%d\n", rank_count[i]);
}
return 0;
}
