模板及讲解
什么是CDQ分治
CDQ 分治就是将询问和修改(初值)都离线，然后对其分治的一种方法。
具体就是每次将区间一分为二，然后只统计左边修改对右边询问的影响，以此类推。
CDQ分治解决什么问题
CDQ 分治一般用来降维。比如有题需要树状数组套平衡树则可以降至只用树状数组解决。
CDQ 分治优点是将询问和修改隔离，即转为静态问题，且常数较小。缺点必须离线。
CDQ 分治的实现与归并排序类似。
二维偏序
例题：Luogu 3374
已知一个数列，你需要进行下面两种操作：
1、将某一个数加上$x$
2、求区间和
将原数组先改为修改。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MAXN = 500000 + 5;
struct data {
LL pos, tp, x;
bool operator < (const data &rhs) {
return pos == rhs.pos ? tp < rhs.tp : pos < rhs.pos; // 修改优先于查询
}
} cz[MAXN * 4], b[MAXN * 4];
LL n, m, tot, xwtot, ans[MAXN];
void CDQ(LL l, LL r) {
if (l >= r) return ;
LL M = (l + r) >> 1ll;
CDQ(l, M), CDQ(M + 1ll, r);
LL t1 = l, t2 = M + 1ll, cnt = 0ll, sum = 0ll;
while (t1 <= M && t2 <= r) {
if (cz[t1] < cz[t2]) { // 只处理左边修改
if (cz[t1].tp == 1) sum += cz[t1].x;
++cnt, b[cnt] = cz[t1++];
} else { // 只处理右边询问
if (cz[t2].tp == 2) ans[cz[t2].x] -= sum;
if (cz[t2].tp == 3) ans[cz[t2].x] += sum;
++cnt, b[cnt] = cz[t2++];
}
}
while (t1 <= M) {
if (cz[t1].tp == 1) sum += cz[t1].x;
++cnt, b[cnt] = cz[t1++];
}
while (t2 <= r) {
if (cz[t2].tp == 2) ans[cz[t2].x] -= sum;
if (cz[t2].tp == 3) ans[cz[t2].x] += sum;
++cnt, b[cnt] = cz[t2++];
} // 将没有归并完的继续并
for (LL i = l; i <= r; ++i) cz[i] = b[i - l + 1];
}
void clean() {
tot = xwtot = 0ll;
}
int solve() {
clean();
scanf("%lld%lld", &n, &m);
for (LL x, i = 1ll; i <= n; ++i) {
scanf("%lld", &x);
cz[++tot] = (data){i, 1ll, x}; // 原数组上的每一位变成区间加操作
}
for (LL tp, x, y, i = 1ll; i <= m; ++i) {
scanf("%lld%lld%lld", &tp, &x, &y);
if (tp == 1) {
cz[++tot] = (data){x, 1ll, y};
} else {
cz[++tot] = (data){x - 1ll, 2ll, ++xwtot};
cz[++tot] = (data){y, 3ll, xwtot}; // 询问区间拆成前缀和相减
}
}
CDQ(1ll, tot);
for (LL i = 1; i <= xwtot; ++i) printf("%lld\n", ans[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
三维偏序
例题：Bzoj 3262
给出$n$个三元组$(x_i,y_i,z_i)$，对于每个三元组求有几个三元组$(x_j,y_j,z_j)$满足$x_i \geq x_j, y_i \geq y_j,z_i \geq z_j$
将第一维排序，然后第二维用 CDQ 分治。第三维再用权值 BIT 来找答案。
注意要去重，因为>=会使得相同的三元组互相影响。
写时注意：
1、根据题目偏序要求定
flw[t1].y <= flw[t2].y的比较符
2、排序要三维都单调
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 200000 + 5;
struct data {
int x, y, z, id, sz; // 三维，flw 哪个位置，有几个数相同(内部大小)
bool operator != (const data &rhs) const {
return !(x == rhs.x && y == rhs.y && z == rhs.z);
}
} whw[MAXN], flw[MAXN], b[MAXN]; // whw: 输入数组 flw: 去重后数组 b: CDQ辅助数组
int n, k, ans[MAXN], tax[MAXN], sz[MAXN]; // 每个去重后不算内部影响的答案，最后的答案，没有归并之前的大小
int a[MAXN], stp[MAXN], tot;
bool cmp(data ra, data rb) {
if (ra.x == rb.x) {
if (ra.y == rb.y) return ra.z < rb.z;
else return ra.y < rb.y;
} else return ra.x < rb.x; // 全部都要单调
}
int lowbit(int x) {return x & (-x);}
void add(int x, int v) {
for (int i = x; i <= k; i += lowbit(i)) a[i] += v;
}
int query(int x) {
int ret = 0;
for (int i = x; i > 0; i -= lowbit(i)) ret += a[i];
return ret;
}
void cl(int x) { // 清空当前树状数组
for (int i = x; i <= k; i += lowbit(i)) a[i] = 0;
}
void CDQ(int l, int r) {
int M = (l + r) >> 1;
if (l >= r) return ;
CDQ(l, M), CDQ(M + 1, r);
int t1 = l, t2 = M + 1, cnt = 0;
tot = 0;
while (t1 <= M && t2 <= r) {
if (flw[t1].y <= flw[t2].y) { // <=
add(flw[t1].z, flw[t1].sz), stp[++tot] = flw[t1].z;
b[++cnt] = flw[t1++]; // 只处理左边的增加
} else {
ans[flw[t2].id] += query(flw[t2].z);
b[++cnt] = flw[t2++]; // 只处理右边的查询
}
}
while (t1 <= M) {
b[++cnt] = flw[t1++];
}
while (t2 <= r) {
ans[flw[t2].id] += query(flw[t2].z);
b[++cnt] = flw[t2++];
}
for (int i = 1; i <= tot; ++i) cl(stp[i]); // 清空
for (int i = l; i <= r; ++i) flw[i] = b[i - l + 1];
}
void clean() {
ms(ans, 0), ms(tax, 0), ms(a, 0);
whw[0] = (data){0, 0, 0, 0, 0};
whw[n + 1] = (data){0, 0, 0, 0, 0};
}
int solve() {
scanf("%d%d", &n, &k);
clean();
for (int i = 1; i <= n; ++i) scanf("%d%d%d", &whw[i].x, &whw[i].y, &whw[i].z);
sort(whw + 1, whw + 1 + n, cmp);
tot = 0;
int gg = 0;
for (int i = 1; i <= n + 1; ++i) { // 去重
if (whw[i] != whw[i - 1]) flw[++tot] = whw[i], sz[tot - 1] = flw[tot - 1].sz = gg, gg = 1, flw[tot].id = tot; else ++gg;
}
int lstn = n; n = tot - 1;
CDQ(1, n);
for (int i = 1; i <= n; ++i) ans[i] += sz[i] - 1;
for (int i = 1; i <= n; ++i) tax[ans[i]] += sz[i];
for (int i = 0; i < lstn; ++i) printf("%d\n", tax[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
最优化问题
斜率优化$x, k$都不单调：Bzoj 1492，Loj 2483
1、注意斜率不存在时INF的正负。
2、注意CDQ分治时q[i].id与i的区别
