[cdq分治]简易教程&学习笔记
我不是柳橙汁
2017-12-17 21:15:27
[原帖地址](https://www.cnblogs.com/mlystdcall/p/6219421.html)
前言
辣鸡蒟蒻\_\_stdcall终于会CDQ分治啦！
CDQ分治是我们处理各类问题的重要武器。它的优势在于可以顶替复杂的高级数据结构，而且常数比较小；缺点在于必须离线操作。
CDQ分治的基本思想和实现都很简单，但是因为没有人给本蒟蒻详讲，所以我对着几篇论文头疼了一个下午，最终在menci和sxysxy大佬的帮助下学会了CDQ分治。本文介绍一些非常simple的CDQ分治问题，目的在于帮助新手更快地入门CDQ分治，希望对大家有帮助。
转载请注明作者：\_\_stdcall。
基本思想
CDQ分治的基本思想十分简单。如下：
我们要解决一系列问题，这些问题一般包含修改和查询操作，可以把这些问题排成一个序列，用一个区间[L,R]表示。
分。递归处理左边区间[L,M]和右边区间[M+1,R]的问题。
治。合并两个子问题，同时考虑到[L,M]内的修改对[M+1,R]内的查询产生的影响。即，用左边的子问题帮助解决右边的子问题。
这就是CDQ分治的基本思想。和普通分治不同的地方在于，普通分治在合并两个子问题的过程中，[L,M]内的问题不会对[M+1,R]内的问题产生影响。
具体实现和用途
二维偏序问题
给定N个有序对(a,b)，求对于每个(a,b)，满足a2<a且b2<b的有序对(a2,b2)有多少个。
我们从归并排序求逆序对来引入二维偏序问题。
回忆一下归并排序求逆序对的过程，我们在合并两个子区间的时候，要考虑到左边区间的对右边区间的影响。即，我们每次从右边区间的有序序列中取出一个元素的时候，要把“以这个元素结尾的逆序对的个数”加上“左边区间有多少个元素比他大”。这是一个典型的CDQ分治的过程。
现在我们把这个问题拓展到二维偏序问题。在归并排序求逆序对的过程中，每个元素可以用一个有序对(a,b)表示，其中a表示数组中的位置，b表示该位置对应的值。我们求的就是“对于每个有序对(a,b)，有多少个有序对(a2,b2)满足a2<a且b2>b”，这就是一个二维偏序问题。
注意到在求逆序对的问题中，a元素是默认有序的，即我们拿到元素的时候，数组中的元素是默认从第一个到最后一个按顺序排列的，所以我们才能在合并子问题的时候忽略a元素带来的影响。因为我们在合并两个子问题的过程中，左边区间的元素一定出现在右边区间的元素之前，即左边区间的元素的a都小于右边区间元素的a。
那么对于二维偏序问题，我们在拿到所有有序对(a,b)的时候，先把a元素从小到大排序。这时候问题就变成了“求顺序对”，因为a元素已经有序，可以忽略a元素带来的影响，和“求逆序对”的问题是一样的。
考虑二维偏序问题的另一种解法，用树状数组代替CDQ分治，即常用的用树状数组求顺序对。在按照a元素排序之后，我们对于整个序列从左到右扫描，每次扫描到一个有序对，求出“扫描过的有序对中，有多少个有序对的b值小于当前b值”，可以用 权值树状数组/权值线段树 实现。然而当b的值非常大的时候，空间和时间上就会吃不消，便可以用CDQ分治代替，就是我们所说的“顶替复杂的高级数据结构”。别急，一会儿我们会看到CDQ分治在这方面更大的用途。
二维偏序问题的拓展
给定一个N个元素的序列a，初始值全部为0，对这个序列进行以下两种操作：
操作1：格式为1 x k，把位置x的元素加上k（位置从1标号到N）。
操作2：格式为2 x y，求出区间[x,y]内所有元素的和。
这是一个经典的树状数组问题，可以毫无压力地秒掉，现在，我们用CDQ分治解决它——带修改和查询的问题。
我们把他转化成一个二维偏序问题，每个操作用一个有序对(a,b)表示，其中a表示操作到来的时间，b表示操作的位置，时间是默认有序的，所以我们在合并子问题的过程中，就按照b从小到大的顺序合并。
问题来了：如何表示修改与查询？
具体细节请参见代码，这里对代码做一些解释，请配合代码来看。我们定义结构体Query包含3个元素：type，idx，val，其中idx表示操作的位置，type为1表示修改，val表示“加上的值”。而对于查询，我们用前缀和的思想把他分解成两个操作：sum[1,y]-sum[1,x-1]，即分解成两次前缀和的查询。在合并的过程中，type为2表示遇到了一个查询的左端点x-1，需要把该查询的结果减去当前“加上的值的前缀和”，type为3表示遇到了一个查询的右端点y，需要把查询的结果加上当前“加上的值的前缀和”，val表示“是第几个查询”。这样，我们就把每个操作转换成了带有附加信息的有序对(时间，位置)，然后对整个序列进行CDQ分治。
有几点需要注意：
对于位置相同的操作，要先修改后查询。
代码中为了方便，使用左闭右开区间。
合并问题的时候统计“加上的值的前缀和”，只能统计左边区间内的修改操作，改动查询结果的时候，只能修改右边区间内的查询结果。因为只有左边区间内的修改值对右边区间内的查询结果的影响还没有统计。
代码中，给定的数组是有初始值的，可以把每个初始值变为一个修改操作。
代码如下：
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXN = 500001; // 原数组大小
const int MAXM = 500001; // 操作数量
const int MAXQ = (MAXM<<1)+MAXN;
int n,m;
struct Query {
int type, idx; ll val;
bool operator<( const Query &rhs ) const { // 按照位置从小到大排序，修改优先于查询
return idx == rhs.idx ? type < rhs.type : idx < rhs.idx;
}
}query[MAXQ];
int qidx = 0;
ll ans[MAXQ]; int aidx = 0; // 答案数组
Query tmp[MAXQ]; // 归并用临时数组
void cdq( int L, int R ) {
if( R-L <= 1 ) return;
int M = (L+R)>>1; cdq(L,M); cdq(M,R);
ll sum = 0;
int p = L, q = M, o = 0;
while( p < M && q < R ) {
if( query[p] < query[q] ) { // 只统计左边区间内的修改值
if( query[p].type == 1 ) sum += query[p].val;
tmp[o++] = query[p++];
}
else { // 只修改右边区间内的查询结果
if( query[q].type == 2 ) ans[query[q].val] -= sum;
else if( query[q].type == 3 ) ans[query[q].val] += sum;
tmp[o++] = query[q++];
}
}
while( p < M ) tmp[o++] = query[p++];
while( q < R ) {
if( query[q].type == 2 ) ans[query[q].val] -= sum;
else if( query[q].type == 3 ) ans[query[q].val] += sum;
tmp[o++] = query[q++];
}
for( int i = 0; i < o; ++i ) query[i+L] = tmp[i];
}
int main() {
scanf( "%d%d", &n, &m );
for( int i = 1; i <= n; ++i ) { // 把初始元素变为修改操作
query[qidx].idx = i; query[qidx].type = 1;
scanf( "%lld", &query[qidx].val ); ++qidx;
}
for( int i = 0; i < m; ++i ) {
int type; scanf( "%d", &type );
query[qidx].type = type;
if( type == 1 ) scanf( "%d%lld", &query[qidx].idx, &query[qidx].val );
else { // 把查询操作分为两部分
int l,r; scanf( "%d%d", &l, &r );
query[qidx].idx = l-1; query[qidx].val = aidx; ++qidx;
query[qidx].type = 3; query[qidx].idx = r; query[qidx].val = aidx; ++aidx;
}
++qidx;
}
cdq(0,qidx);
for( int i = 0; i < aidx; ++i ) printf( "%lld\n", ans[i] );
return 0;
}
```
三维偏序问题
给定N个有序三元组(a,b,c)，求对于每个三元组(a,b,c)，有多少个三元组(a2,b2,c2)满足a2<a且b2<b且c2<c。
不用CDQ分治的方法：先按照a元素排序，从左到右扫描。按照b元素构造权值树状数组，树状数组每个节点按照c元素构造平衡树。树套树的解法不仅常数大，而且代码量巨大，还容易写错。
类似二维偏序问题，先按照a元素从小到大排序，忽略a元素的影响。然后CDQ分治，按照b元素从小到大的顺序进行归并操作。但是这时候没办法像 求逆序对 一样简单地统计 个数 了，c元素如何处理呢？
这时候比较好的方案就是借助权值树状数组。每次从右边的序列中取出三元组(a,b,c)时，对树状数组查询c值小于(a,b,c)的三元组有多少个；每次从左边序列取出三元组(a,b,c)的时候，根据c值在树状数组中进行修改。注意，每次使用完树状数组记得把树状数组归零！详细代码我会放在下面一道例题中。
三维偏序问题的拓展
平面上有N个点，每个点的横纵坐标在[0,1e7]之间，有M个询问，每个询问为查询在指定矩形之内有多少个点，矩形用(x1,y1,x2,y2)的方式给出，其中(x1,y1)为左下角坐标，(x2,y2)为右上角坐标。
不用CDQ分治的话可以用二维线段树或者二维树状数组来做，然而空间是明显吃不消的。用CDQ分治如何做呢？
到这里大家应该比较清楚了吧，把每个点的位置变成一个修改操作，用三元组(时间，横坐标，纵坐标)来表示，把每个查询分解成4个前缀和查询，同样用三元组来表示。对于修改操作，每个三元组没有附加信息；对于查询操作，每个三元组的附加信息为“第几个查询”和“对结果的影响是+还是-，用+1表示+，用-1表示-”。操作到来的时间是默认有序的，分治过程中按照横坐标从小到大排序，用树状数组维护纵坐标的信息。代码如下：
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
using namespace std;
const int MAXN = 500001; // 点的数量
const int MAXM = 500001; // 询问数量
const int MAXQ = MAXN+(MAXM<<2);
const int MAXL = 10000002; // 树状数组大小
int n, m, maxy = -1;
namespace IO { // 快读相关
const int BUFSZ = 1e7;
char buf[BUFSZ]; int idx, end;
void init() { idx = BUFSZ; }
char getch() {
if( idx == BUFSZ ) {
end = fread( buf, 1, BUFSZ, stdin ); idx = 0;
}
if( idx == end ) return EOF;
return buf[idx++];
}
int getint() {
int num = 0; char ch;
while( isspace(ch=getch()) );
do { num = num*10 + ch-'0'; } while( isdigit(ch=getch()) );
return num;
}
}
using IO::getint;
struct Query {
int type, x, y, w, aid; // w表示对查询结果贡献(+还是-)，aid是“第几个查询”
bool operator<( const Query &rhs ) const {
return x == rhs.x ? type < rhs.type : x < rhs.x;
}
}query[MAXQ];
int qidx = 0;
void addq( int type, int x, int y, int w, int aid ) {
query[qidx++] = (Query){type,x,y,w,aid};
}
int ans[MAXM], aidx = 0;
namespace BIT { // 树状数组相关
int arr[MAXL];
inline int lowbit( int num ) { return num&(-num); }
void add( int idx, int val ) {
while( idx <= maxy ) {
arr[idx] += val;
idx += lowbit(idx);
}
}
int query( int idx ) {
int ans = 0;
while( idx ) {
ans += arr[idx];
idx -= lowbit(idx);
}
return ans;
}
void clear( int idx ){
while( idx <= maxy ) {
if( arr[idx] ) arr[idx] = 0; else break;
idx += lowbit(idx);
}
}
}
Query tmp[MAXQ];
void cdq( int L, int R ) {
if( R-L <= 1 ) return;
int M = (L+R)>>1; cdq(L,M); cdq(M,R);
int p = L, q = M, o = L;
while( p < M && q < R ) {
if( query[p] < query[q] ) {
if( query[p].type == 0 ) BIT::add( query[p].y, 1 );
tmp[o++] = query[p++];
} else {
if( query[q].type == 1 ) ans[query[q].aid] += query[q].w * BIT::query( query[q].y );
tmp[o++] = query[q++];
}
}
while( p < M ) tmp[o++] = query[p++];
while( q < R ) {
if( query[q].type == 1 ) ans[query[q].aid] += query[q].w * BIT::query( query[q].y );
tmp[o++] = query[q++];
}
for( int i = L; i < R; ++i ) {
BIT::clear( tmp[i].y ); // 清空树状数组
query[i] = tmp[i];
}
}
int main() {
IO::init(); n = getint(); m = getint();
while( n-- ) {
int x,y; x = getint(); y = getint(); ++x; ++y; // 为了方便，把坐标转化为[1,1e7+1]
addq(0,x,y,0,0); maxy = max( maxy, y ); // 修改操作无附加信息
}
while( m-- ) {
int x1,y1,x2,y2; x1 = getint(); y1 = getint(); x2 = getint(); y2 = getint(); ++x1; ++y1; ++x2; ++y2;
addq(1,x1-1,y1-1,1,aidx); addq(1,x1-1,y2,-1,aidx); addq(1,x2,y1-1,-1,aidx); addq(1,x2,y2,1,aidx); ++aidx;
maxy = max( maxy, max(y1,y2) );
}
cdq(0,qidx);
for( int i = 0; i < aidx; ++i ) printf( "%d\n", ans[i] );
return 0;
}
```
总结
对于经典的多维偏序问题和多维数据结构的查询和修改，我们可以用一步步“降维”的方式解决。排序，数据结构，CDQ分治都是我们降维的工具。
CDQ分治还有其他很多强大的功能，比如多重嵌套CDQ分治，用CDQ分治加速动态规划等等。总的来说就是可以顶一层数据结构，降维用。由于本文是面向我这样的新手的教程，而且我也没有学这些用法(我好弱啊QAQ)，所以对于这些更难一点的问题不作介绍。
习题（参考menci博客）
园丁的烦恼 SHOI2007 BZOJ 1935
【模板】树状数组 1 luogu P3374
Mokia BZOJ 1176
陌上花开 BZOJ 3262
简单题BZOJ 2683
动态逆序对 CQOI2011 BZOJ 3295