神秘分治 学习笔记

前言

个人认为分治是一种神秘的算法，尤其是你在调代码的时候。

• 什么是分治？

分治其实是一种思想，通过将一个大范围的问题分成许多小范围问题来求解。
对，就是「分以治之」。
这难免会想到一些与之相似的算法，像二分、动态规划，但这其实还是有区别的。
至于具体怎么个区别，本蒟蒻语文水平有限，还是自己体会吧。

cdq分治

介绍

cdq分治最早由IOI金牌得主陈丹琦在高中整理并总结，cdq分治也因此而得名。
cdq分治并不是一种具体的算法，而是一种思想，有十分强大的扩展性。
其主要应用于以下方面：

• 多维偏序问题
• 动态规划优化转移

其主要思想是将一些复杂问题转化为偏序问题进行求解，同时cdq分治是一种离线思想，处理不了强制在线的问题，如果出现了强制在线的偏序问题那本蒟蒻只能洗洗睡了。

二维偏序

• 停停停，还没有说什么是偏序呢。

其实偏序的定义说了也看不懂

偏序关系

设 \(R\) 是集合 \(A\) 上的一个二元关系，若 \(R\) 满足：

• 自反性：\(\forall x\in A,xRx\)
• 反对称性：\(\forall x,y\in A\) 若 \(xRy,yRx\) 则 \(x=y\)。
• 传递性：\(\forall x,y,z\in A\) 若 \(xRy,yRz\) 则 \(xRz\)。

则称 \(R\) 为 \(A\) 上的偏序关系，通常记作 \(≼\)

其实可以把 $R$ 理解成 $\le$、$\ge$ 之类的东西。

下面就开始正式的二位偏序了。

• 为什么不从一维开始？
• 因为一维没什么东西。

最著名的二位偏序问题就是逆序对个数问题，即求解一个排列中满足：

• 下标 \(i < j\)。
• 值 \(a_i>a_j\)。

这样的数对的对数，这也就是二位偏序中的那「二维」。
想必已经不是第一次看这样的题了，想一想这道题可以用什么方法做？

• 树状数组/线段树
• 归并排序

其实这些就是cdq分治的思想。

• 对于树状数组，统计前面所有点对当前的贡献，我们按下标顺序依次填入(在其所对应的值上添加 \(1\))，在填入一个值之前，查询比当前值小的有多少个，并累计在答案中。
• 对于归并排序，统计左区间对右区间的贡献，我们将一个区间 \([l,r]\) 按 \([l,mid]\)、\([mid+1,r]\) 分成两个子区间向下递归，回溯时，左右两个区间内部已经各自拍好序，用双指针同时扫两个区间，因为左区间的下标一定小于右区间的下标，所以只需要统计对于右区间的每一个数，在左区间内有多少个比它小的，统计在答案中即可。

其实使用归并排序或树状数组的前提都是其中一位偏序——下标是有序的，也就是说归并排序和树状数组都只能干掉其中的一维偏序。

从二位到三维

陌上花开（三维偏序）\(^{luoguP3810}\)

题目中的三维偏序是很显然的，那要怎么做呢？
既然归并排序和树状数组都能干掉一维偏序，那么它俩结合起来不就能干两维了吗，那剩下的一维怎么整？
直接排序就行了。
也就是说，对于三维偏序问题，对于每一维我们分别使用：

1. sort排序
2. 归并排序（cdq分治）
3. 树状数组

就可以轻松干掉这道题了。
唯一注意的一点在排序的cmp函数！？

#include<bits/stdc++.h>
using namespace std;
const int NUM=1e6+10;struct node{int s,c,m,id,op;
}q[NUM],tmp[NUM];
int ans[NUM];
int anss[NUM];
int n,k,tot;
int C[NUM];
void add(int x,int val){for(int i=x;i<=k;i+=(i&-i)) C[i]+=val;
}
int sum(int x){int ans=0;for(int i=x;i;i-=(i&-i)) ans+=C[i];return ans;
}void cdq(int l,int r){if(l==r) return;int mid=(l+r)>>1;cdq(l,mid),cdq(mid+1,r);int i=l,j=mid+1,k=i;while(i<=mid&&j<=r){if(q[i].c<=q[j].c){if(!q[i].op) add(q[i].m,1);tmp[k++]=q[i++];}else{if(q[j].op) ans[q[j].id]+=sum(q[j].m);tmp[k++]=q[j++];}}while(j<=r){if(q[j].op) ans[q[j].id]+=sum(q[j].m);tmp[k++]=q[j++];}for(int p=l;p<i;++p) if(!q[p].op) add(q[p].m,-1);while(i<=mid){tmp[k++]=q[i++];}for(int i=l;i<=r;++i) q[i]=tmp[i];
}int main(){cin>>n>>k;for(int i=1,x,y,z;i<=n;++i){cin>>x>>y>>z;q[++tot]={x,y,z,i,0};q[++tot]={x,y,z,i,1};}sort(q+1,q+1+tot,[](node x,node y){if(x.s!=y.s) return x.s<y.s;if(x.c!=y.c) return x.c<y.c;if(x.m!=y.m) return x.m<y.m;return x.op<y.op;});cdq(1,tot);for(int i=1;i<=tot;++i){if(q[i].op){anss[ans[q[i].id]-1]++;}}for(int i=0;i<n;++i){cout<<anss[i]<<'\n';}return 0;
}

从三维偏序到多维偏序

【模板】离线静态四维数点\(^{luoguP14957}\)

还在叠加。
上面说过，使用sort排序、归并排序、树状数组可以干掉三维，现在就只剩下了一维。
可不可以用线段树？
我不是把线段树和树状数组放一块了吗，它俩是一个东西。
不过貌似好像也许真的可以用树套树去做，不过本蒟蒻树套树是贺的。
既然树套树不行，可以cdq套cdq啊！
具体过程如下：

1. 在主函数中案第一维排好序。
2. 在cdq1中左区间打上标记 \(0\)，右区间打上标记 \(1\)，并按第二维排序，传入cdq2。
3. 在cdq2中使用双指针扫描左右区间，当且仅当左区间的一个值的标记为 \(0\)，才能对右区间做出贡献，将其添入树状数组，但且仅当右区间的一个值的标记为 \(1\) 才可以从树状数组中获取贡献并累计到答案中。

其实会了四维，五维、六维什么的也都不在话下了。

#include<bits/stdc++.h>
using namespace std;
const int NUM=10e5+10;
const int NUMM=100e5+10;int n,m;
struct node{int x,y,x2,y2,op,id,tag;
}A[NUM],tmp[NUM];
int tot,num;
int cpy[NUMM],cnt;
int C[NUM];
int ans[NUM];
void add(int x,int val){for(int i=x;i<=cnt+10;i+=(i&-i)) C[i]+=val;
}
int sum(int x){int res=0;for(int i=x;i;i-=(i&-i)) res+=C[i];return res;
}
int lb(int x){return lower_bound(cpy+1,cpy+1+cnt,x)-cpy;
}
void cdq2(int l,int r){if (l == r) return;int mid=(l+r)>>1;cdq2(l,mid),cdq2(mid+1,r); int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(A[i].x2<=A[j].x2){if(!A[i].tag&&!A[i].op) add(A[i].y2,1);tmp[k++]=A[i++];}else{if(A[j].tag&&A[j].op) ans[A[j].id]+=sum(A[j].y2);tmp[k++]=A[j++];}}while(j<=r){if(A[j].tag&&A[j].op) ans[A[j].id]+=sum(A[j].y2);tmp[k++]=A[j++];}for(int p=l;p<i;++p) if(!A[p].tag&&!A[p].op) add(A[p].y2,-1);while(i<=mid) tmp[k++]=A[i++];for(int i=l;i<=r;++i) A[i]=tmp[i];
} void cdq1(int l,int r){if(l==r) return;int mid=(l+r)>>1;cdq1(l,mid),cdq1(mid+1,r);for(int i=l;i<=mid;++i) A[i].tag=0;for(int i=mid+1;i<=r;++i) A[i].tag=1;stable_sort(A+l,A+r+1,[](node x,node y){if(x.y!=y.y) return x.y<y.y;if(x.x2!=y.x2) return x.x2<y.x2;return x.y2<y.y2;});cdq2(l,r);
}signed main(){cin>>n>>m;for(int i=1,x,y,x2,y2;i<=n;++i){cin>>x>>y>>x2>>y2;cpy[++cnt]=-y2;A[++tot]={x,y,-x2,-y2,0,0,0};}for(int i=1,x,y,x2,y2;i<=m;++i){cin>>x>>y>>x2>>y2;cpy[++cnt]=-y2;A[++tot]={x,y,-x2,-y2,1,i,0};}sort(cpy+1,cpy+1+cnt);cnt=unique(cpy+1,cpy+1+cnt)-cpy;for(int i=1;i<=tot;++i){A[i].y2=lb(A[i].y2);}stable_sort(A+1,A+1+tot,[](node x,node y){if(x.x!=x.y) return x.x<y.x;if(x.y!=y.y) return x.y<y.y;if(x.x2!=y.x2) return x.x2<y.x2;return x.y2<y.y2;});cdq1(1,tot);for(int i=1;i<=m;++i){cout<<ans[i]<<'\n';}return 0;
}

整体二分

介绍

二分答案自然是一种很好的算法，虽然这会使你的算法复杂度多加一个 \(log\)，但在大多数情况都无伤大雅，但偏偏就有有些时候多加一个 \(log\) 就会死，这就不得不请出整体二分了。
如果说二分答案会让你的程序多加一个 \(log\)，那么整体二分则是将那个 \(n\) 换成 \(log\)，听起来非常厉害，在实现上其实是将全部寻问一次查完。

实现

其在是线上类似于cdq分治，将一个大区间分成两个小区间，并将寻问分到对应的区间中去。

【模板】可持久化线段树 2\(^{luoguP3834}\)

等等，这不是主席树的题吗？
寻问区间第 \(k\) 大整体二分也可以干呢，而且无论时间还是空间都比主席树更优，唯一的缺点可能就是整体二分是离线算法，而主席树则是在线算法。
这可能就是离线算法的特点了吧。
好了回归正题。
具体做法就是扫描属于当前值域的全部操作（注意在整体二分的时候，将原数列当成添加操作），先扫描添加操作，在扫描查询操作，并用树状数组维护区间元素个数。
设当前值域区间为 \([l,r]\)，重点为 \(mid\)。
如果当前操作时添加一个数：

• 若当前元素在 \([l,mid]\) 之间，则将其填入树状数组，并放入左区间的临时数组。
• 若当前元素在 \([mid+1,r]\) 之间，则直接将其放入右区间的临时数组。

如果当前操作时查询：
首先在树状数组中查询当前操作所要查询的区间的元素个数(当然，时小于 \(mid\) 的元素个数)，记为 \(cnt\)。

• 若 \(cnt\ge k\) 说明答案在左区间，将其放入左区间的临时数组。
• 若 \(cnt < k\) 说明答案在右区间，讲 \(k\) 减去 \(cnt\) ，并将其放入右区间临时数组（相当于在右区间查询 \(k-cnt\)，根权值线段树查排名的值一个思路）。

最后别往了：

• 将临时数组中的数放到查询数组中。
• 清空树状数组。

一个好理解但空间会爆炸的代码（vector存储）：

#include<bits/stdc++.h>
using namespace std;
const int NUM=5e6+10;struct oper{int t;int l,r,k,id;
}; int n,m;
int a[NUM],ans[NUM];
int C[NUM];
void add(int x,int val){for(int i=x;i<=n;i+=(i&-i)) C[i]+=val;
}
int sum(int x){int ans=0;for(int i=x;i;i-=(i&-i)) ans+=C[i];return ans;
}
int query(int l,int r){return sum(r)-sum(l-1);
}
void sol(int l,int r,vector<oper>& ops){if(ops.empty()) return;if(l==r){for(auto& op:ops){if(op.t==1){ans[op.id]=l;}}return;}int mid=(l+r)>>1;vector<oper> left,right;for(oper& op:ops){if(op.t==0){if(op.k<=mid){add(op.l,1);left.push_back(op);}else{right.push_back(op);}}}for(oper& op:ops){if(op.t==1){int cnt=query(op.l,op.r);if(cnt>=op.k){left.push_back(op);}else{op.k-=cnt;right.push_back(op);}}}for(oper& op:ops){if(op.t==0&&op.k<=mid) add(op.l,-1);}sol(l,mid,left);left.clear();sol(mid+1,r,right);right.clear();
}int main(){cin>>n>>m;int minn=INT_MAX,maxx=INT_MIN;for(int i=1;i<=n;++i){cin>>a[i];minn=min(minn,a[i]);maxx=max(maxx,a[i]);}vector<oper> ops;for(int i=1;i<=n;++i){ops.push_back({0,i,0,a[i],0});}for(int i=1;i<=m;++i){int l,r,k;cin>>l>>r>>k;ops.push_back({1,l,r,k,i});}sol(minn,maxx,ops);for(int i=1;i<=n;++i){cout<<ans[i]<<'\n';}return 0;
}

整体二分的竞赛风写法（数组存储）：

#include<bits/stdc++.h>
using namespace std;const int NUM=1e6+10;
const int inf=0x3f3f3f3f;struct node{int l,r,v,id;
}q[NUM],tp[NUM];
int n,m,a[NUM],len;
int C[NUM],ans[NUM];
inline void add(int x,int val){for(int i=x;i<=n;i+=(i&-i)) C[i]+=val;
}
inline int sum(int x){int ans=0;for(int i=x;i;i-=(i&-i)) ans+=C[i];return ans;
}
void clear(int x){for(int i=x;i<=n;i+=(i&-i)) C[i]=0; 
}
inline void sol(int ql,int qr,int l,int r){if(l==r){while(ql<=qr){if(q[ql].id) ans[q[ql].id]=l;++ql;}return;}int mid=(l+r)>>1,il=ql,ir=qr;for(int i=ql;i<=qr;++i){if(!q[i].id){if(q[i].v<=mid) add(q[i].l,1),tp[il++]=q[i];else tp[ir--]=q[i];}else{int cnt=sum(q[i].r)-sum(q[i].l-1);if(cnt>=q[i].v) tp[il++]=q[i];else q[i].v-=cnt,tp[ir--]=q[i];}}for(int i=ql;i<il;++i){q[i]=tp[i];if(!q[i].id&&q[i].v<=mid) clear(q[i].l);}for(int i=il;i<=qr;++i){q[i]=tp[qr-i+il];}if(il!=ql) sol(ql,ir,l,mid);if(ir!=qr) sol(il,qr,mid+1,r);
}int main(){cin>>n>>m;for(int i=1;i<=n;++i){cin>>a[i];q[i]={i,i,a[i],0};}sort(a+1,a+1+n);len=unique(a+1,a+1+n)-a-1;for(int i=1;i<=n;++i){q[i].v=lower_bound(a+1,a+1+len,q[i].v)-a;}for(int i=1;i<=m;++i){cin>>q[i+n].l>>q[i+n].r>>q[i+n].v;q[i+n].id=i;}sol(1,n+m,1,len);for(int i=1;i<=m;++i){cout<<a[ans[i]]<<'\n';}return 0;
}

提示：
双倍经验：可怜的狗狗\(^{louguP1533}\)
你甚至连改都不用改。

猫树分治

在学猫树分治前，应先学习猫树。

介绍

其实猫树分治没多少东西，类似于前面的分治算法，在跑猫树的时候计算答案即可。

好吃的题目\(^{luoguP6240}\)

一道猫树套DP的题。
数据范围过大，预处理数组开不开？
于是我们考虑在跑猫树的时候计算答案。
对于区间背包的合并，可以这样做:

\[ans=\max_{j=0}^{t_i}\{f[l_i][j]+f[r_i][t_i-j]\} \]

#include <bits/stdc++.h>
using namespace std;
const int NUM1=6e4+10;
const int NUM2=2e2+10;
const int NUM3=2e5+10;
struct node{int l,r,t;
}q[NUM3];
int n,m;
int h[NUM3],w[NUM3];
int f[NUM1][NUM2];
int p[NUM3],s[NUM3],tot;
int ans[NUM3];void sol(int l,int r,int tl,int tr){if(tl>tr) return;int mid=(l+r)>>1,tmid=tl-1;for(int i=0;i<=200;++i) f[mid][i]=0;for(int i=mid+1;i<=r;++i){for(int j=0;j<h[i];++j) f[i][j]=f[i-1][j];for(int j=h[i];j<=200;++j){f[i][j]=max(f[i-1][j],f[i-1][j-h[i]]+w[i]);}}for(int i=h[mid];i<=200;++i) f[mid][i]=w[mid];for(int i=mid-1;i>=l;--i){for(int j=0;j<h[i];++j) f[i][j]=f[i+1][j];for(int j=h[i];j<=200;++j){f[i][j]=max(f[i+1][j],f[i+1][j-h[i]]+w[i]);}}int tt=0;for(int i=tl;i<=tr;++i){int x=p[i];if(q[x].r<=mid) p[++tmid]=x;else if(q[x].l>mid) s[++tt]=x;else{int res=0;for(int j=0;j<=q[x].t;++j){res=max(res,f[q[x].l][j]+f[q[x].r][q[x].t-j]);}ans[x]=res;}}for(int i=1;i<=tt;++i) p[tmid+i]=s[i];tr=tmid+tt;sol(l,mid,tl,tmid);sol(mid+1,r,tmid+1,tr); 
}signed main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;++i){cin>>h[i];}for(int i=1;i<=n;++i){cin>>w[i];}for(int i=1;i<=m;++i){cin>>q[i].l>>q[i].r>>q[i].t;if(q[i].l==q[i].r){if(q[i].t>=h[q[i].l]) ans[i]=w[q[i].l];}else p[++tot]=i;}sol(1,n,1,tot);for(int i=1;i<=m;++i){cout<<ans[i]<<'\n';}
}

后记

感觉写博客也是件很累的事。
猫树分治那里一是没学太明白，而是累了写不动，过几天继续干。
累了，睡了。