CDQ分治（基于归并排序的分治）
CDQ分治
预备知识
分治
与传统分治相同，CDQ分治的核心思想也是分而治之。
对于一个数组序列上的问题，分治的思想是总是考虑中的
这一部分，而对于
这一求解函数则使用递归表示。
式子中的加号并不一定是加法，只表示答案的合并。
这个说法有点过于抽象了。
举个例子，例如：分治求最大子段和。
区间字段和问题是指，给你一个大小为的数组，数组元素的值有正有负，然后请你求出数组中权值和最大的子数组。
在这个问题中表示：“区间
中权值和最大的子数组之和”，而"+"并不是指把三者相加求和，而是对三者的答案取max。
仅表示左端点落在
,右端点落在
这些子区间提供的答案，因为其他区间一定在递归的过程中被穷举到了，不必考虑。
当然，设计分治算法最关心的还是这一部分的求法，由于在分治的过程中每递归一次都会使得范围缩小一半，所以在求解
时哪怕暴力穷举区间元素，总复杂度仍为
。
在“最大子段和”问题中的求解方法为从mid开始向左右延伸，分别记录后缀和、前缀和的最大值，然后相加求和即可。
分治与线段树
线段树很多时候可以解决“带修改的分治问题”，用线段树解决“动态分治”类的问题时一般都为单点修改，不涉及lazytag。
那么静态分治和使用线段树动态分治的区别在哪里？
区别在于，分治法考虑的是，而
往往暴力求。
线段树由于无法接受每次修改都暴力的复杂度，则必须想办法只考虑
。
举个例子：“带修改的最大子段和问题”
线段树节点除了维护，也就是“区间
中权值和最大的子数组之和”这一答案以外，还需要额外维护，从左侧延伸的最大和，从右侧延伸的最大和。
换句话说就是得想办法把给维护了。
树分治与点分树
同上，树分治与点分树的关系就是数组分治与线段树的关系。
偏序约束条件
偏序问题是一个挺老生常谈的问题。
基本上就是说某一种东西有那么2~3种属性，然后给你两个这个东西，当他们的每种属性之间都必须满足一些给定的大小关系时，约束条件成立。
举两个例子，一个是逆序对问题，一个是最长上升子序列问题。这些都是最典型的“偏序约束条件”。
逆序对问题指给你一个长度为n的数组a。
问你有多少对i,j满足约束条件：
最长上升子序列的问题则可以表示成，当满足约束条件：
时，可以进行状态转移。
CDQ分治擅长处理“偏序约束关系”，所以想要使用CDQ分治的话最核心的部分就是找约束关系或者将问题的限制条件转化为这种偏序约束条件。
基于归并排序
CDQ分治在归并排序的过程中处理“偏序约束条件”，为了讲解它的运行原理，我们模拟一个归并排序的过程。
例如将数组进行归并排序
如图所示是一个归并树结构，蓝色的字体代表下标。
最底层是排序前的数组，经过log层归并排序后，变为了数值从小到大升序排列。
但看某一次的归并过程，一次归并在归并树中涉及到了三个节点：当前节点，左子树，右子树。
然后易知，在归并过程中，处于同一个节点块内的元素总是数值有序的。同时，来自左子树块中的元素的下标，总是小于来自右子树块内元素的下标。
如果只考虑来自左子树的块内元素与来自右子树块内元素的偏序问题。发现在本次归并排序的过程中又恰好同时被满足了。
假设某种偏序约束条件是对a,b两种属性进行约束的话。CDQ分治首先需要做的是按照属性a排序，然后做关于属性b的归并排序。
基于时间轴
在使用CDQ代替树套树、树套树套树等复杂数据结构时，CDQ分治的一大特点是基于时间轴做分治。
但是与其说是特点，倒不如说其实是为了构造偏序约束条件，将操作的时间戳也当成是节点的某一种属性。
CDQ分治的应用
分治求逆序对
分治求最长上升子序列
分治求线段覆盖
分治求区间元素种类数
分治求动态凸包
分治求区间和（单点修改）
分治求区间和（区间修改）
分治求区间和（区间加等差）
分治求逆序对
这里以NC14310逆序数为例题。
https://ac.nowcoder.com/acm/problem/15163
分治求逆序对应该算CDQ分治入门级别的例题了。
需要满足的约束条件是：，满足条件后要做的操作是
。
根据我们的预备知识，所有的分治算法无外乎都是考虑，中的
这一部分。
其中仅表示
落在
,
落在
这些数对提供的答案。其他贡献递归算法自动帮我们算好了，所以仅需要考虑一层。
还是以数组为例讲解算法的过程。
如图是归并排序合并和
这两有序数组的过程。
由于仅表示
落在
,
落在
的数对，所以每当从右侧弹出数字的时候，我们只要知道左侧已经弹出几个数字。把他们加到最终答案中，
就处理完了。
如果记归并排序过程中左侧有序数组的指针为的话，每当从右侧弹出数字时都计算贡献
，逆序对就算完了。
#include
using namespace std;
const int MAXN=100005;
int n,a[MAXN],temp[MAXN];
long long ans;
void cdqDivAlgorithm(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdqDivAlgorithm(l,mid);
cdqDivAlgorithm(mid+1,r);
int p1=l,pl=l,p2=mid+1;
while(p1<=mid&&p2<=r){
if(a[p1]>a[p2]){
temp[pl++]=a[p1++];
}else{
temp[pl++]=a[p2++];
ans+=p1-l;
}
}
while(p1<=mid){
temp[pl++]=a[p1++];
}
while(p2<=r){
temp[pl++]=a[p2++];
ans+=p1-l;
}
for(int i=l;i<=r;++i){
a[i]=temp[i];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
cdqDivAlgorithm(1,n);
printf("%lld\n",ans);
return 0;
}
分治求最长上升子序列
这里以NC16810拦截导弹为例题。
题意很简单，给n个数求
1、最长非升子序列。
2、最长严格下降子序列。
讲道理两问处理起来区别不大，改写一下排序规则即可。
对于第一问，需要满足的约束条件是：
，在满足约束条件的前提下进行状态转移%7D)
。
对于第二问，需要满足的约束条件是：
，在满足约束条件的前提下进行状态转移。
还是以数组
为例讲解算法的过程，假设先求第一问，最长非升子序列。
如图是归并排序合并和
这两有序数组的过程。
CDQ分治只解决偏序约束条件下的转移问题，实际上直接改造状态转移方程就可以适应不同的情况。（比如权值和最大上升子序列）
算法实现的难点
由于是做动态规划，所以还必须注意状态转移的阶段性。
最长上升子序列的其中一种划分阶段的方法是按照下标递增的顺序进行划分求解。
在处理上，借助“中序遍历”的思路就可以一遍分治，一遍满足状态转移的阶段性。
但是“中序遍历”又不能满足归并排序（归并排序必须是后序遍历）。所以在实际处理上先进行一遍朴素的归并排序并记录归并过程，然后模拟归并（已经排好了，不需要真的再排一遍），采取“中序遍历”的递归模式，在过程中进行状态转移。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,x,dp[MAXN],a[MAXN],ans;
pair<int,int>temp[MAXN][20];//<val,pos>
bool cmp(const pair<int,int> &A,const pair<int,int> &B,const int &type){
return type?A.first!=B.first?A.first>B.first:A.second<B.second:A.first!=B.first?A.first<B.first:A.second>B.second;
}
void mergeSort(int l,int r,int deep,const int &cmptype){
if(l==r){
temp[l][deep].first=a[l];
temp[l][deep].second=l;
return;
}
int mid=(l+r)>>1;
mergeSort(l,mid,deep+1,cmptype);
mergeSort(mid+1,r,deep+1,cmptype);
int p1=l,p2=mid+1;
while(p1<=mid&&p2<=r){
if(cmp(temp[p1][deep+1],temp[p2][deep+1],cmptype)){
temp[l++][deep]=temp[p1++][deep+1];
}else{
temp[l++][deep]=temp[p2++][deep+1];
}
}
while(p1<=mid){
temp[l++][deep]=temp[p1++][deep+1];
}
while(p2<=r){
temp[l++][deep]=temp[p2++][deep+1];
}
}
void cdqDivAlgorithm(int l,int r,int deep,const int &cmptype){
if(l==r){
dp[l]=max(dp[l],1);
ans=max(ans,dp[l]);
return;
}
int mid=(l+r)>>1;
cdqDivAlgorithm(l,mid,deep+1,cmptype);
int p1=l,p2=mid+1,premax=0;
while(p1<=mid&&p2<=r){
if(cmp(temp[p1][deep+1],temp[p2][deep+1],cmptype)){
premax=max(premax,dp[temp[p1++][deep+1].second]);
}else{
dp[temp[p2][deep+1].second]=max(premax+1,dp[temp[p2][deep+1].second]);
p2++;
}
}
while(p2<=r){
dp[temp[p2][deep+1].second]=max(premax+1,dp[temp[p2][deep+1].second]);
p2++;
}
cdqDivAlgorithm(mid+1,r,deep+1,cmptype);
}
int main()
{
while(scanf("%d",&x)!=EOF)a[++n]=x;
mergeSort(1,n,0,1);
cdqDivAlgorithm(1,n,0,1);
printf("%d\n",ans);
memset(dp,0,sizeof(dp));
ans=0;
mergeSort(1,n,0,0);
cdqDivAlgorithm(1,n,0,0);
printf("%d\n",ans);
return 0;
}
分治求线段覆盖
这里以线段覆盖为例题
需要满足的约束条件是：
，在满足约束条件的前提下进行状态转移%7D)
。
这个约束条件看着别扭，所以我们稍微扩展一下变成
。其实这个
约束不起作用，因为只要输入的线段合法，当满足时也必定被满足。
多扩展这个无用的约束有两点意义
1、构造偏序约束条件
2、l有序实际上是做状态转移的阶段，为了保证动态规划的阶段性所以引入这个约束。
接下来要做的事就和“分治求最长上升子序列”大同小异了。
CDQ分治只解决偏序约束条件下的转移问题，实际上直接改造状态转移方程就可以适应不同的情况。（比如带权线段覆盖问题）
算法难点
首先是这个约束和之前不一样，也就是到当前层的时候我们既需要l有序，又需要r有序。为了让左子树的r有序，右子树的l有序。一开始按照l排序，然后在中序遍历的时候进行状态转移。
然后我们知道归并排序算法必须是“后序遍历”，所以在代码实现上，我们中序处理状态转移，后序处理归并排序。
使用CDQ处理复杂结构体时尽量不要封装，频繁拷贝可能会导致大常数。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int n,L[MAXN],R[MAXN],id[MAXN],dp[MAXN],ans;
int temp[MAXN];
void cdqDivAlgorithm(int l,int r){
if(l==r){
dp[id[l]]=max(1,dp[id[l]]);
ans=max(ans,dp[id[l]]);
return;
}
int mid=(l+r)>>1;
cdqDivAlgorithm(l,mid);
int p1=l,pl,p2=mid+1,premax=0;
while(p1<=mid&&p2<=r){
if(R[id[p1]]<=L[id[p2]]){
premax=max(premax,dp[id[p1++]]);
}else{
dp[id[p2]]=max(premax+1,dp[id[p2]]);
++p2;
}
}
while(p2<=r){
dp[id[p2]]=max(premax+1,dp[id[p2]]);
++p2;
}
cdqDivAlgorithm(mid+1,r);
p1=l,pl=l,p2=mid+1;
while(p1<=mid&&p2<=r){
if(R[id[p1]]<R[id[p2]]){
temp[pl++]=id[p1++];
}else{
temp[pl++]=id[p2++];
}
}
while(p1<=mid){
temp[pl++]=id[p1++];
}
while(p2<=r){
temp[pl++]=id[p2++];
}
for(int i=l;i<=r;++i){
id[i]=temp[i];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d %d",&L[i],&R[i]);
id[i]=i;
}
sort(id+1,id+1+n,[](const int &A,const int &B){
return L[A]<L[B];
});
cdqDivAlgorithm(1,n);
printf("%d\n",ans);
return 0;
}
分治求区间元素种类数
[SDOI2009]HH的项链为例
乍一看别说偏序约束条件，连一个顺序约束条件都找不出来。难点在于如何转化问题。 我们想，如果只统计一个数字在所查询的区间中第一次出现的情况，最终的答案也就是区间种类数。
我们记数组中第
个位置上一次在数组中出现相同数字的位置为
，如果不存在上一次出现相同数字的位置，则记为-1。
这时候就可以写出约束条件了。
问题转化成满足约束条件：
时，进行操作
。
注意
这个条件当然要拆分，但是你不要拆完了约束条件变为
三元的约束条件。
这样不是不能做，而是最终做出来的算法复杂度是
的。
这个拆分呢，借助前缀和的思想去拆分就好了。可以看成是，满足
的数目减去满足
的数目。
那么也就将约束条件，转化为了满足
的值减去满足
的值。
然后这个约束条件其实看着不太舒服，所以令
，把原来的约束条件中的符号换一下，让它好看一点。
即满足
时，如果代表数组元素，
代表查询，则进行操作或者满足
时
。
在代码的处理上，我们多加m个操作，让这些操作的
，这样的话两种操作就都整理成这种逆序对的一般形式了，然后最终计算贡献的时候乘上再-1。
然后接下来就是CDQ分治最擅长的部分了，直接搞就可以了。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3000005;
int n,m,x,L[MAXN],R[MAXN],id[MAXN],type[MAXN],pre[MAXN/3],ans[MAXN],temp[MAXN],f[MAXN];
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
inline int getq(int x)
{
if(x>n)x-=n;
if(x>m)x-=m;
return x;
}
void cdqDivAlgorithm(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdqDivAlgorithm(l,mid);
cdqDivAlgorithm(mid+1,r);
int p1=l,pl=l,p2=mid+1,sum=0;
while(p1<=mid&&p2<=r){
if(R[id[p1]]<=R[id[p2]]){
if(type[id[p1]]==0)++sum;
temp[pl++]=id[p1++];
}else{
if(type[id[p2]]==1)
ans[getq(id[p2])]+=sum*f[id[p2]];
temp[pl++]=id[p2++];
}
}
while(p1<=mid){
temp[pl++]=id[p1++];
}
while(p2<=r){
if(type[id[p2]]==1)
ans[getq(id[p2])]+=sum*f[id[p2]];
temp[pl++]=id[p2++];
}
for(int i=l;i<=r;++i){
id[i]=temp[i];
}
}
int main()
{
n=read();
memset(pre,-1,sizeof(pre));
for(int i=1;i<=n;++i){
id[i]=i,L[i]=pre[x=read()],R[i]=i;
pre[x]=i;
type[i]=0;
}
m=read();
for(int i=1;i<=m;++i){
id[n+i]=n+i;
L[n+i]=read();
R[n+i]=read();
type[n+i]=1;
f[n+i]=1;
id[n+m+i]=n+m+i;
L[n+m+i]=L[n+i];
R[n+m+i]=L[n+i]-1;
type[n+m+i]=1;
f[n+m+i]=-1;
}
sort(id+1,id+1+n+m*2,[](const int &A,const int &B){
return L[A]!=L[B]?L[A]<L[B]:type[A]>type[B];
});
cdqDivAlgorithm(1,n+m*2);
for(int i=1;i<=m;++i){
printf("%d\n",ans[i]);
}
return 0;
}
分治求动态凸包
[JSOI2008]Blue Mary开公司为例
这个应该是CDQ最多的使用场景。那为什么求个凸包和偏序扯上关系了呢，它本来也没关系。 问题就在于，单调队列/单调栈这玩意太菜了，这个算法垃圾。它要求你给出的直线的斜率必须是单调增或者减的，总之得有单调性。然后查询最好也有单调性，如果查询不具有单调性也能查，不过得在单调栈里面二分。如果两个都不单调就凉了。有个叫李超树的东西用单
就能在线插入直线，查询凸包点值。甚至还能
插入线段，而且常数还比较小。
为了拯救单调栈/队列，首先看一下它的使用条件。
1、按照时间顺序插入的直线斜率单调。
2、按照时间顺序进行查询点值的x坐标单调。
那么要想使用单调栈解决动态凸壳问题，对于任意一对插入的直线
需要满足约束条件：
同理，对于任意一对进行的查询也要满足约束条件：
然后一看这个限制条件那肯定CDQ分治啊，从t有序归并到k,x有序即可。然后因为插入直线总是在左子树才执行，查询总是在右子树才执行，所以插入的直线按k排，查询按x排同时进行即可。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
const double eps=1e-6;
int m,n,id[MAXN],qid[MAXN],type[MAXN],x[MAXN],temp[MAXN],top;
double k[MAXN],b[MAXN],ans[MAXN];
char op[55];
inline bool cmp(const int &A,const int &B){
return type[A]!=type[B]?type[A]<type[B]:type[A]?x[A]<x[B]:k[A]<k[B];
}
inline int dcmp(double x){
return x>eps?1:x<-eps?-1:0;
}
inline double getCross(const double &k1,const double &b1,const double &k2,const double &b2){
return (b2-b1)/(k1-k2);
}
inline double getVal(const double &k,const double &b,const int &x)
{
return k*x+b;
}
pair<double,double>stk[MAXN];
void stkClear(){
top=0;
stk[++top]=make_pair(0,0);
}
void stkInsert(double k,double b){
if(dcmp(stk[top].first-k)==0 && dcmp(stk[top].second-b)<0)top--;
if(dcmp(stk[top].first-k)==0 && dcmp(stk[top].second-b)>=0)return;
while(top>=2&&dcmp(getCross(stk[top].first,stk[top].second,stk[top-1].first,stk[top-1].second)-getCross(stk[top].first,stk[top].second,k,b))>0)top--;
stk[++top]=make_pair(k,b);
}
double stkQuery(int x){
while(top>=2&&dcmp(getVal(stk[top].first,stk[top].second,x)-getVal(stk[top-1].first,stk[top-1].second,x))<0)--top;
return getVal(stk[top].first,stk[top].second,x);
}
void cdqDivAlgorithm(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdqDivAlgorithm(l,mid);
cdqDivAlgorithm(mid+1,r);
stkClear();
for(int i=l;i<=mid && !type[id[i]];++i){
stkInsert(k[id[i]],b[id[i]]);
}
for(int i=r;i>mid && type[id[i]];--i){
ans[qid[id[i]]]=max(ans[qid[id[i]]],stkQuery(x[id[i]]));
}
int p1=l,pl=l,p2=mid+1;
while(p1<=mid&&p2<=r){
if(cmp(id[p1],id[p2])){
temp[pl++]=id[p1++];
}else{
temp[pl++]=id[p2++];
}
}
while(p1<=mid){
temp[pl++]=id[p1++];
}
while(p2<=r){
temp[pl++]=id[p2++];
}
for(int i=l;i<=r;++i){
id[i]=temp[i];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
id[i]=i;
scanf("%s",op);
if(*op=='P'){
type[i]=0;
scanf("%lf %lf",&b[i],&k[i]);
b[i]-=k[i];
}
else{
type[i]=1;
qid[i]=++m;
scanf("%d",&x[i]);
}
}
cdqDivAlgorithm(1,n);
for(int i=1;i<=m;++i){
printf("%d\n",(int)ans[i]/100);
}
return 0;
} 分治求区间和（单点修改）
当是修改,是查询，则有满约束条件：
时进行操作
,其中t代表时间戳。
利用前缀和进行拆分，变成满足约束
时，满足约束
时
。
接下来同分治求逆序对。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int T,id[MAXN],sum[MAXN],type[MAXN],n,m,k,qid[MAXN],ans[MAXN],val[MAXN],l,r,pos[MAXN],f[MAXN],temp[MAXN];
char op[55];
void cdqDivAlgorithm(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
cdqDivAlgorithm(l,mid);
cdqDivAlgorithm(mid+1,r);
int p1=l,pl=l,p2=mid+1,sum=0;
while(p1<=mid&&p2<=r){
if(pos[id[p1]]<=pos[id[p2]]){
if(type[id[p1]]==0)
sum+=val[id[p1]];
temp[pl++]=id[p1++];
}else{
if(type[id[p2]]==1)
ans[qid[id[p2]]]+=f[id[p2]]*sum;
temp[pl++]=id[p2++];
}
}
while(p1<=mid){
temp[pl++]=id[p1++];
}
while(p2<=r){
if(type[id[p2]]==1)
ans[qid[id[p2]]]+=f[id[p2]]*sum;
temp[pl++]=id[p2++];
}
for(int i=l;i<=r;++i){
id[i]=temp[i];
}
}
int main(){
scanf("%d",&T);
for(int cas=1;cas<=T;++cas){
scanf("%d",&n);
m=0;
k=0;
for(int i=1;i<=n;++i){
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
while(scanf("%s",op)){
if(*op=='Q'){
scanf("%d %d",&l,&r);
type[++m]=1;
id[m]=m;
ans[qid[m]=++k]=sum[r]-sum[l-1];
pos[m]=r;
f[m]=1;
type[++m]=1;
id[m]=m;
qid[m]=k;
pos[m]=l-1;
f[m]=-1;
}else if(*op=='A'){
type[++m]=0;
id[m]=m;
scanf("%d",&pos[m]);
scanf("%d",&val[m]);
}else if(*op=='S'){
type[++m]=0;
id[m]=m;
scanf("%d",&pos[m]);
scanf("%d",&val[m]);
val[m]=-val[m];
}else{
break;
}
}
cdqDivAlgorithm(1,m);
printf("Case %d:\n",cas);
for(int i=1;i<=k;++i){
printf("%d\n",ans[i]);
}
}
return 0;
}
分治求区间和（区间修改）、分治求区间和（区间加等差）
对于区间加数，做一次差分后变为单点修改区间查询，就变成了这种形式。
区间加等差数列或者区间加任意多项式也是同理，维护相应阶数的差分数组即可。
只不过计算贡献时，不是简单的数值而是多项式。
CDQ分治的意义
如果一道题只用到了一层CDQ，那这道题也一定能用其他数据结构解决，所以一般大家都见不到这个算法。
不过不愿意写李超树和动态凸壳的人用CDQ分治来解动态凸壳的斜率优化问题倒是挺常见的。
由于CDQ分治本身不使用其他任何数据结构，这表示我们还留有底牌。即使现在在做的问题上再加一维，直接把线段树等结构套进去就能做。
说人话就是CDQ分治可以避免一部分的树套树，以及树套树套树。（还有一部分可以使用整体二分的思路去避免高级数据结构堆叠）
个人觉得分治类算法无论是泛用性还是上限都很高，在允许暴力枚举当前分治的区间的前提下复杂度是优秀的
，如果题目复杂需要嵌套其他数据结构时，也比纯数据结构套数据结构来的更容易，但是在算法竞赛中又往往被忽视（一般遇到一个题先想用个什么数据结构去维护）。
程序=算法+数据结构，而不是数据结构的嵌套和堆叠。
拼多多集团-PDD公司氛围 515人发布