CDQ 分治简单小结

从围棋说起

? 围棋是一门深奥的竞技艺术。虽然说最近人类棋手已在机器的手下再无抬头之力，但是人类棋手下棋时的策略却对我们很有启发性 (毕竟目前 AlphaGo 还不能告诉你为什么它要这么下棋)。

围棋遵从三个简单的规则：

• 双方在没有子的格点上轮流落子，共 19*19 个格点
• 一个被敌方棋子围住 4 个面的棋子被移除棋盘 (即所谓吃)
• 最终占有棋盘目数最多的棋手胜出 (如果出现了双方互吃停不下来的情况, 那两个目平分)

? 这极其简单的规则却使得其成为了一个一定可以分出胜负的有穷游戏。

? 在围棋竞技时，棋手往往会由如下的方法分析当前的局势 (最初的 AlphaGo 似乎也是这么做的)：

• 局部估价：考虑一个小范围内各个棋子之间的相互作用
• 整体估价：分析整体上棋子群的相互影响

? 在使用前一个方法时，棋手往往会精确地将每个小范围划分为几个计算群，对于每个计算群进行他所认为的最优策略的模拟来得出这个局部的可行策略。通过这个方法棋手可以精确设计出博弈的策略。

? 在使用后一个方法时，棋局往往在他们眼中化为了相互作用的气体。整体与整体之间发生宏观的相互作用，使得每个局部产生宏观上的的优势与劣势之分。通过这个方法棋手可以大致知道博弈的战略。

? 仔细思考这两个分析方法，我们会发现，一副复杂异常的棋局，其每个棋子之间的相互作用难以量化计算，但是我们却可以知道棋子整体之间的作用趋势。就好比我们难以分析星体每个分子之间的相互作用，但是我们却可以从宏观上应用万有引力定律。这便是从整体入手对问题简化的好处。

? 所以无论整体二分、CDQ 分治，都在做这样一个事情：当一个大的问题难以处理时，我们会处理这个大问题的几个子问题之间的关系，再分别去处理这几个子问题。

如何划分问题

? 我们先来看这样几个问题：

• 求一个数列的逆序对数
• 动态求平面上距一个坐标 (x,y) 曼哈顿距离最近的点到该坐标的曼哈顿距离。
• 动态求三维空间中一个长方体内包裹了几个已给出的点

? 显然，这些问题当我们直接分析时复杂度总是比较坑爹。比如第一个问题，我们早就知道可以做到 $O(nlogn)$求解，但是直接枚举逆序对时只能做到 $O(n^2)$。所以我们就从逆序对这个简单的问题来看看分治的思想是如何简化问题的解决的。

? 对于一个序列，我们按照围棋棋手的思想，分析这个序列左右两半互相的影响。显然左边的有一些数可能会比右边的一些数大，而这些数就给答案产生了贡献。我们仔细分析会发现，这样的一些数与数的关系是满足一个单调性的：左边的 $x$比右边的 $a$个数大，左边的 $y$比右边的 $b$个数大，当 $a<=y$时一定有 $b<=a$。这种单调性在没有划分序列之前是不存在的。而就是这样的单调性可以使运算大大简化。

? 如果我们继续将已经划分的左右两半递归的划分，那么一定可以通过这种划分得到所有的上述关系，进而得出逆序对总数。后两个问题将在后面说道。

为什么可以简化运算

? 刚才说道将问题划分为子问题是可以获得十分有利的单调性的。至于这点单调性的作用到底有多大，我们暂时还得不到量化的分析。但是可以明确一点，有了单调性，计算问题的时间复杂度一定会降低。于是乎，下面我们将引入一些数学。

? 拿逆序对的例子来说，若原问题的规模是 $n$，那么两个子问题的规模就是 $\frac{n}{2}$，所以我们可以知道：
$$
T(n)=2T(\frac{n}{2})+n
$$
? 其中的右侧余项 $n$是处理两个子部分之间的影响的复杂度。在逆序对问题中，这个部分可以利用归并排序在 $O(n)$的复杂度内被完成。所以下面我们需要求满足这个式子的函数。

方法 1：猜想法

? 猜测：$T(n)=nlogn$满足条件

? 证明：
$$
2T(\frac{n}{2})+n=2(\frac{n}{2}log\frac{n}{2})+n=nlogn=T(n)
$$

方法 2：树分析法

? 对于递归到不同层数时的总复杂度，我们可以画出这样的一棵二叉树。每个子节点的规模是父节点的一半，所以可以知道每一层的复杂度总和就是 n。由于这样的二叉树最多有 $logn$层，所以我们可以知道总时间复杂度就是 $O(nlogn)$

? 通过如上的分析，我们可以知道对于逆序对问题，这种整体之间的单调性的确可以使时间复杂度获得很大的降低。

主定理 (Master Theorem)

? 对于这一类问题求解方法的时间复杂度，我们给出一个比较普适的计算方法：
$$
T(n)=a\cdot T(\frac{n}{b})+f(n)
$$

• case1:$f(n)n^{log_ba}$时，且是多项式级别的大于，$T(n)=O(f(n))$

  说明：

  ? 由树分析法可得：

$$
T(n)=O(n^{log_ba})+\sum\limits_{j=0}^{log_bn-1}a^jf(n/b^j)
$$

• case1: 当 f(n) 非常便宜时，递归树每层的成本将主要随节点数增多而成几何级数增长，其成本在叶节点处达到最高，故叶节点的 $O(n^{log_ba})$占主导地位。分治的总时间复杂度渐进等于叶节点时间复杂度和。
• case2: 当 f(n) 的成本为 $n^{log_ba}$时，第 k 层的成本为 $n^{log_ba}$，第 k+1 层的成本为 $a(\frac{n}{b})^{log_ba}=n^{log_ba}$，所以每一层的代价相等。分治的总代价为层数乘每层代价。
• case3: 当 f(n) 非常昂贵时，递归树每层的成本成集合级数递减，其成本在第一层最高，故第一层的 O(f(n)) 占主导地位。分治的总时间复杂度渐进等于树根的时间复杂度。

如何进行分治

? 类比逆序对问题，我们可以知道该分治算法的基本步骤：划分，递归，合并。划分是指将总问题划分为两个子问题，递归指递归处理两个子问题，合并指计算两个子问题间的影响。

? 长篇大论总不如一个直击重点的例子有用。

动态求平面上距一个坐标 (x,y) 曼哈顿距离最近的点到该坐标的曼哈顿距离。

? 对于这个问题，我们先来分析 “位于询问坐标的第三象限的点”。

? 由图我们可以知道，到询问坐标曼哈顿距离最近的第三象限点一定是第三象限内 x+y 最大的。所以我们需要求解的问题可以化简为：求已知的点中满足 $x\leq x_0,y\leq y_0$的最大 $x+y$。而这个问题很适合用 CDQ 分治解决。

? 我们可以将所有的询问和插入操作离线，那么问题再度转化：对于每个 $t_0$时刻的询问求满足 $t\leq t_0,x\leq x_0,y\leq y_0$的插入操作的最大 $x+y$。按照逆序对问题的思想，我们需要找到一种划分问题的方式，使得子问题之间的影响具有单调性。其实我们可以将 t,x,y 中的任意一个从中间分开。拿时间举例，前一半时间内的插入操作都有可能影响后一半时间内的询问操作。现在我们只需要知道：后一半时间内的某个询问，在前一半时间内有几个插入操作 x 和 y 均不大于它。这时候，我们将前一半时间内的插入操作按 x 升序排序，后一半时间内的询问操作也按 x 升序排序，这样我们又获得了一个有关 x 的单调性，只需要再用树状数组查询 “小于定值的 y 有多少个” 就可以了。伪代码是：

struct query[10000];
void cdq(int l,int r)
{
  cdq(l,mid),cdq(mid+1,r);
  对 [l,mid] 和 [mid+1,r] 分别进行 x 升序排序;
  for(i=mid+1 to r)
  {
    将前一半时间内 x 比 query[i].x 小的插入操作的 x+y 都放入树状数组的第 y 位
    查询树状数组中前 query[i].y 中 x+y 的最大值，将答案累加到 query[i].ans 中
  }
  清空树状数组
}

? 对于其他象限内的点，我们可以采用线性变换将所有点绕某个中心旋转后重复同样的计算即可。

动态求三维空间中一个长方体内包裹了几个已给出的点

? 我们发现这个问题要考虑的东西好像比上一个问题多了一层。这个问题涉及到了 $t,x,y,z$四个变量之间的关系。不过不急，我们先分析一个：如何用简单的询问构造对长方体的询问。显然，可以用容斥原理将 8 个询问拼凑成一个长方体。这 8 个询问将可以是非常简单的询问：求满足 $t\leq t_0,x\leq x_0,y\leq y_0,z\leq z_0$的点的个数。

? 接着，由于这是一个 4 维的问题，而之前我们谈的都是 3 维及以下的问题：“逆序对”=2D，“平面点对 “=3D。因此，这一次我们也许需要借助一些比树状数组更特殊的数据结构，或者……

? CDQ 分治套 CDQ 分治：先不考虑 z 维的影响。对前 3 维做 CDQ 分治。这时，插入树状数组 (或者什么数据结构) 的东西就成了一个 2 维的东西 (y,z)，询问的也是这样的二维的东西。对于这个二维的东西，我们也是有其 “时间，y，z” 三个分量。因此对于这 3 个分量我们可以再次使用 CDQ 分治。这也就是 CDQ 套 CDQ。具体代码请见文章最下方。

? 这一种算法的时间复杂度实际上是 $O(nlog^3n)$的。但是根据主定理 case3，复杂度应该是 $O(nlog^2n)$啊？这时由于主定理中的大于小于号均表示多项式级别的大于，此算法的复杂度是 $T(n)=2T(\frac{n}{2})+nlog^2n$，应该属于 case2。这个结论也可以通过树分析法较方便地求出。

代码

逆序对问题 (CodeVS1688)

? 虽然说简单逆序对这种二维偏序问题可以直接使用树状数组求解，但是我们也不妨试试 CDQ 分治 (即归并排序)。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int t[200000],arr[200000];
int n;
unsigned long long num=0;

void msort(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)/2;
    int a=l,b=mid+1,c=1;
    msort(l,mid),msort(mid+1,r);
    while(a<=mid&&b<=r)
        if(arr[a]>arr[b])t[c++]=arr[b++],num+=mid-a+1;
        else t[c++]=arr[a++];
    while(a<=mid)t[c++]=arr[a++];
    while(b<=r)t[c++]=arr[b++];
    for(int i=1;i<=r-l+1;i++)arr[l-1+i]=t[i];
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    msort(1,n);
    printf("%d\n",num);
    return 0;
}

动态曼哈顿距离最近点问题 (BZOJ2716)

? 类似的题目还有 BZOJ2648，但是这道题貌似只能用 K-Dtree 解决，CDQ 分治估计是卡不过去的。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 2100011
#define Y0 1000002
using namespace std;

typedef struct tquery
{
    int typ,x,y,f,id,t;
    tquery(){}
    tquery(int typ,int x,int y,int f,int id,int t)
        :typ(typ),x(x),y(y),f(f),id(id),t(t){}
}query;
query qur[MX];
int sum[MX],ans[MX];
int n,m,qnum,onum;
bool cmpt(query a,query b){return a.t<b.t;}
bool cmpx(query a,query b){return a.x<b.x;}
void add(int p,int x){for(;p<MX;p+=p&-p)sum[p]=max(sum[p],x);}
int get(int p){int x=-MX;for(;p;p-=p&-p)x=max(x,sum[p]);return x;}
void del(int p){for(;p<MX;p+=p&-p)sum[p]=-MX;}
void input()
{
    int o,a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);a++,b++;
        onum++;
        qur[onum]=query(0,a,b,a+b,0,onum);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&o);
        onum++;
        if(o==1)
        {
            scanf("%d%d",&a,&b);a++,b++;
            qur[onum]=query(0,a,b,a+b,0,onum);
        }
        else
        {
            scanf("%d%d",&a,&b);a++,b++;
            qur[onum]=query(1,a,b,a+b,++qnum,onum);
        }
    }
}
void rot()
{
    int x,y;
    for(int i=1;i<=onum;i++)
    {
        x=qur[i].x,y=qur[i].y;
        qur[i].x=Y0-y;
        qur[i].y=x;
        qur[i].f=qur[i].x+qur[i].y;
    }
}
void cdq(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1,p=l;
    cdq(l,mid),cdq(mid+1,r);
    for(int i=mid+1;i<=r;i++)
    {
        if(!qur[i].typ)continue;
        while(p<=mid&&qur[p].x<=qur[i].x)
        {
            if(!qur[p].typ)add(qur[p].y,qur[p].f);
            p++;
        }
        ans[qur[i].id]=min(ans[qur[i].id],qur[i].f-get(qur[i].y));
    }
    for(int i=l;i<p;i++)if(!qur[i].typ)del(qur[i].y);
    inplace_merge(qur+l,qur+mid+1,qur+r+1,cmpx);
}
int main()
{
    memset(ans,0x3f,sizeof(ans));
    memset(sum,0x9f,sizeof(sum));
    input();
    sort(qur+1,qur+onum+1,cmpt);
    cdq(1,onum);
    rot();
    sort(qur+1,qur+onum+1,cmpt);
    cdq(1,onum);
    rot();
    sort(qur+1,qur+onum+1,cmpt);
    cdq(1,onum);
    rot();
    sort(qur+1,qur+onum+1,cmpt);
    cdq(1,onum);
    for(int i=1;i<=qnum;i++)printf("%d\n",ans[i]);
    return 0;
}

三维空间长方体内点数 (HDU5126)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 400005

using namespace std;

typedef struct tquery
{
    int typ,x,y,z,f,q;
}query;
query qur[MX],QUR[MX];
int sum[MX];
int real[MX],ans[MX];
int n,qnum,onum,rnum;
inline bool cmpx(query a,query b){return a.x<b.x;}
inline bool cmpy(query a,query b){return a.y<b.y;}
inline void add(int p,int x){for(;p<=rnum;p+=p&-p)sum[p]+=x;}
inline int get(int p){int x=0;for(;p;p-=p&-p)x+=sum[p];return x;}
inline int gfake(int x){return lower_bound(real+1,real+rnum+1,x)-real;}
inline void lsh()
{
    sort(real+1,real+rnum+1);
    rnum=unique(real+1,real+rnum+1)-real-1;
    for(int i=1;i<=onum;i++)qur[i].z=gfake(qur[i].z);
}
void cdq2(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1,p=l;
    cdq2(l,mid),cdq2(mid+1,r);
    for(int i=mid+1;i<=r;i++)
    {
        if(!QUR[i].typ)continue;
        while(p<=mid&&QUR[p].y<=QUR[i].y)
        {
            if(!QUR[p].typ)add(QUR[p].z,1);
            p++;
        }
        ans[QUR[i].q]+=QUR[i].f*get(QUR[i].z);
    }
    for(int i=l;i<p;i++)if(!QUR[i].typ)add(QUR[i].z,-1);
    inplace_merge(QUR+l,QUR+mid+1,QUR+r+1,cmpy);
}
void cdq1(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1,p=l,q=l;
    cdq1(l,mid),cdq1(mid+1,r);
    for(int i=mid+1;i<=r;i++)
    {
        if(!qur[i].typ)continue;
        while(p<=mid&&qur[p].x<=qur[i].x)
        {
            if(!qur[p].typ)QUR[q++]=qur[p];
            p++;
        }
        QUR[q++]=qur[i];
    }
    cdq2(l,q-1);
    inplace_merge(qur+l,qur+mid+1,qur+r+1,cmpx);
}
void input()
{
    int o,x1,y1,z1,x2,y2,z2;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d%d%d",&x1,&y1,&z1);
            qur[++onum]=(query){0,x1,y1,z1,1,0};
            real[++rnum]=z1;
        }
        else
        {
            scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
            qur[++onum]=(query){1,x2,y2,z2,1,++qnum};
            qur[++onum]=(query){1,x2,y2,z1-1,-1,qnum};
            qur[++onum]=(query){1,x2,y1-1,z2,-1,qnum};
            qur[++onum]=(query){1,x1-1,y2,z2,-1,qnum};
            qur[++onum]=(query){1,x2,y1-1,z1-1,1,qnum};
            qur[++onum]=(query){1,x1-1,y2,z1-1,1,qnum};
            qur[++onum]=(query){1,x1-1,y1-1,z2,1,qnum};
            qur[++onum]=(query){1,x1-1,y1-1,z1-1,-1,qnum};
            real[++rnum]=z1-1,real[++rnum]=z2;
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        onum=qnum=rnum=0;
        memset(ans,0,sizeof(ans));
        input();
        lsh();
        cdq1(1,onum);
        for(int j=1;j<=qnum;j++)printf("%d\n",ans[j]);
    }
    return 0;
}