整体二分
简介
整体二分是一种离线算法，适用于符合以下特征的 DS 题。
- 询问具有可二分性。
- 修改之间互不影响。
- 修改无关答案判定标准。（注意是判定标准而不是判定过程）
- 贡献满足交换律，结合律，可加性。（即答案与操作先后顺序无关，且可加）
允许离线。（废话这是离线算法不允许离线还玩毛线啊）
总体来说，就是把多个二分变成一个二分。
算法流程
统一二分的时候会有两个区间，其中我们用 \([L,R]\) 表示答案区间，用 \([l,r]\) 表示操作区间。
此处的操作可以是修改/查询/etc.
整个过程中我们要维护三个操作集合，第一个集合就是整一个操作集合 \(s\)，还有另外两个操作集合 \(s_1,s_2\)，分别存储对前半区间造成影响的操作和对右半区间造成影响的操作.
每次二分的时候会取答案区间的中点，我们将其记为 \(mid\)，对于会对 \([L,mid]\) 造成影响的操作我们将其存入 \(s_1\)，会对 \((mid,r]\) 造成影响的我们存入 \(s_2\).
当 \(L=R\) 时得出答案即可。
此处以静态区间 kth 为例。
SP3946 MKTHNUM - K-th Number
将原序列中的每个数看作一次插入操作，然后离线即可。
struct opera {
bool type;int x,y,id,k;
}G[N+M];
int n,m;
int ans[M];
int s[N+M],s1[N+M],s2[N+M];
BIT T; // 用 BIT 维护区间中小于等于 mid 的数的个数
void solve(int L,int R,int l,int r) {
if(l>r) return; // 特判，否则就会导致每个答案区间都扫一遍，复杂度爆炸 boom!
if(L==R) { // 边界，存储答案
for(int i=l;i<=r;i++) if(G[s[i]].type) ans[G[s[i]].id]=L;
return;
}
int mid=(L+R)>>1,p1=0,p2=0; // p1,p2 分别表示集合 s1,s2 长度
for(int i=l;i<=r;i++) {
if(G[s[i]].type) {
int res=T.query(G[s[i]].y)-T.query(G[s[i]].x-1);
if(res<G[s[i]].k) {G[s[i]].k-=res;s2[++p2]=s[i];}
else s1[++p1]=s[i];
} else {
if(G[s[i]].x<=mid) T.modify(G[s[i]].id,1);
G[s[i]].x<=mid?s1[++p1]=s[i]:s2[++p2]=s[i];
}
}
for(int i=1;i<=p1;i++) if(!G[s1[i]].type) T.modify(G[s1[i]].id,-1); // 清空
for(int i=1;i<=p1;i++) s[l+i-1]=s1[i];
for(int i=1;i<=p2;i++) s[l+p1-1+i]=s2[i];
solve(L,mid,l,l+p1-1);solve(mid+1,R,l+p1,r);
}
int main() {
// do something...
for(int i=1;i<=n+m;i++) s[i]=i; // 初始化 s 集合，一定要记得！！！
solve(-inf,inf,1,n+m);
// do something...
return 0;
}
而对于动态区间 kth，如 Luogu P2617 Dynamic Rankings 只需把每次修改看作删除一个数再加入一个数即可，其他地方与静态无异。
int p=0;
for(int i=1;i<=m;i++) {
scanf(" %c",&g[++idx].op);
if(g[idx].op=='Q') {
scanf("%d%d%d",&g[idx].l,&g[idx].r,&g[idx].k);
g[idx].id=++p;
} else {
int pos=0,val=0;
scanf("%d%d",&pos,&val);
g[idx].op='D';g[idx].x=pos;g[idx].y=a[pos];
g[++idx].op='C';g[idx].x=pos;g[idx].y=val;
a[pos]=lsh[++tot]=val;
}
}
复杂度分析
用 \(C\) 表示答案区间，\(S\) 表示操作区间，则
\[T(C,S)=T(\frac{C}{2},S_0)+T(\frac{C}{2},S-S_0)+O(f(S)) \leq O(f(n)\log C) \]或者说复杂度是 \(O((n+m)\log C)\)，离散化的话复杂度可以达到 \(O((n+m)\log (n+m))\).
总结
好打好调好理解，好算法。
cdq 分治
简介
cdq 分治常用于计算序列中需要满足某些限制的点对对答案的贡献，通常点对有 \(O(n^2)\) 个。
核心思想
与普通分治类似，把点对分成前半个区间和后半个区间的点对，但 cdq 分治还要处理跨越区间中点的点对，这就是 cdq 分治的核心所在。
算法流程
下面以三维偏序为例。 P3810 【模板】三维偏序（陌上花开）
首先把元素相同的合并，因为 cdq 分治一般解决不了有重复元素的问题，除非重复元素之间不算贡献。
与二维偏序类似，我们把所有元素按 \(a_i,b_i,c_i\) 分别为第一、二、三关键字排序，可以去除一维，变成带顺序限制的二维偏序问题。
此时右区间的每一个点显然都不会对左区间的点产生贡献，那么对左右区间分别按 \(a_i,b_i,c_i\) 为第一、第二关键字排序。观察到此时对于右区间的每一个 \(i\)，符合限制 \(b_j \leq b_i\) 的 \(j\) 一定是左区间的一段随着 \(i\) 增大单调不降的前缀。对于这个前缀查询，用一个 BIT 维护即可。
视值域与序列长度同阶，复杂度为 \(O(n \log^2 n)\).
注意重复元素也有贡献。
struct node {
int a,b,c,cnt,ans,id;
}G[N];
BIT T;
void solve(int l,int r) {
if(l>=r) return;
int mid=(l+r)>>1,le=l;
solve(l,mid);solve(mid+1,r); // 分治计算不跨越中点的点对贡献
std::sort(e+l,e+mid+1,[](node a,node b) {return a.b==b.b?a.c<b.c:a.b<b.b;}); // 注意排序的地址位置
std::sort(e+mid+1,e+r+1,[](node a,node b) {return a.b==b.b?a.c<b.c:a.b<b.b;});
for(int i=mid+1;i<=r;i++) { // 双指针统计答案 其中 i 指向右区间 le 指向左区间
while(le<=mid && e[le].b<=e[i].b) {T.modify(e[le].c,e[le].cnt);le++;}
e[i].ans+=T.query(e[i].c);
}
for(int i=l;i<le;i++) T.modify(e[i].c,-e[i].cnt); // 清空 BIT
}
int main() {
// do something...
std::sort(G+1,G+1+n,[](node a,node b) {return a.a==b.a?(a.b==b.b?a.c<b.c:a.b<b.b):a.a<b.a;});
for(int i=1;i<=n;i++) { // 合并相同元素
if(G[i].a!=G[i-1].a || G[i].b!=G[i-1].b || G[i].c!=G[i-1].c) e[++m]=G[i];
++e[m].cnt;e[m].id=m;
}
solve(1,m);
// do something...
return 0;
}
注意每次分治/排序的时候对边界的计算。
总结
排序的地址有被恶心到一开始调了好久，以后注意。
感觉对分治的理解又加深了，其实以前一直不怎么懂分治。
参考资料
[1] 离线算法入门——整体二分 https://www.cnblogs.com/TianMeng-hyl/p/14977002.html
[2] 分治专题 https://www.cnblogs.com/alex-wei/p/divide_and_conquer.html