0x40「数据结构进阶」例题
CDQ分治
CDQ分治，能够将动态问题转化为静态问题求解。它将操作的时间顺序作为分治的基础，每次递归操作的两部分，回溯时计算前一半的操作对后一半的询问的影响。在实际过程中，它往往用于解决二维平面的动态偏序问题，因而要与排序和树状数组结合。
例题
4701 天使玩偶
计算距离的过程中涉及到了绝对值，为了去掉绝对值符号，我们分四类讨论，即最优解位于询问点的左下，左上，右上，右下四个方向的情况。设目前的询问点为，那么
，四个方向上该式的化简如下：
左下：即
左上：即
右上：即
右下：即
化简原则是将（常量）和
（变量）分开，同时保证四个式子尽量相似（max函数前都为负号）。
因此，我们可以这样做（以左下为例）：
1 将区间内操作对应的点的坐标按照横坐标升序排序。
2 扫描到一个点，就在树状数组中把
个位置和
取max，同时维护前缀和的最大值（注意，树状数组虽然无法维护区间最值，但是当所有区间的起点都为1时，由于不需要用到区间加法，所以树状数组可以胜任）。
3 扫描到一个询问，就在树状数组中查询
上的最大值val，答案就是x+y-val。
上述做法中，排序满足了，树状数组控制了
并维护了
的最大值。
另外三个方向同理，例如左上方，只要按照横坐标升序排序，然后树状数组维护的最大值，修改位置为
，查询时前缀变成
即可。（
也可以是
）
时间复杂度：。
PS：为了保证时间复杂度与询问区间长度有关，我们每次不能建立新的树状数组，而是在每次修改后，都将操作依次撤销。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000000+5;
const int INF=0x3f3f3f3f;
struct node1{
int x,y,op;
}a[maxn];
struct node2{
int x,y,id;
}b[maxn];
int n,m,tot=-INF,c[maxn],ans[maxn];
bool operator<(const node2 &h,const node2 &w){
return h.x<w.x||h.x==w.x&&h.y<w.y;
}
void add(int x,int y){
for(int i=x;i<tot;i+=i&-i) c[i]=max(c[i],y);
}
int ask(int x){
int ans=-INF;
for(int i=x;i>=1;i-=i&-i) ans=max(c[i],ans);
return ans;
}
void cal(int st,int ed,int de,int dx,int dy){
for(int i=st;i!=ed;i+=de){
int y=dy==1?b[i].y:tot-b[i].y;
int temp=dx*b[i].x+dy*b[i].y;
if(a[b[i].id].op==1) add(y,temp);
else ans[b[i].id]=min(ans[b[i].id],temp-ask(y));
}
for(int i=st;i!=ed;i+=de){
int y=dy==1?b[i].y:tot-b[i].y;
if(a[b[i].id].op==1){
for(int j=y;j<tot;j+=j&-j) c[j]=-INF;
}
}
}
void cdq(int l,int r){
int mid=l+r>>1;
if(l<mid) cdq(l,mid);
if(mid+1<r) cdq(mid+1,r);
int t=0;
for(int i=l;i<=r;i++){
if((a[i].op==1&&i<=mid)||(a[i].op==2&&i>mid)){
b[++t].x=a[i].x;
b[t].y=a[i].y;
b[t].id=i;
}
}
sort(b+1,b+t+1);
cal(1,t+1,1,1,1);//左下
cal(1,t+1,1,1,-1);//左上
cal(t,0,-1,-1,1);//右下 这两行里头，xi>=x所以要倒序插入xi
cal(t,0,-1,-1,-1);//右上
}
int main() {
ios::sync_with_stdio(false);
// freopen("天使玩偶.in","r",stdin);
cin>>n>>m;
m+=n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
// a[i].y++;
a[i].op=1;
tot=max(a[i].y,tot);
}
for(int i=n+1;i<=m;i++){
cin>>a[i].op>>a[i].x>>a[i].y;
// a[i].y++;
tot=max(a[i].y,tot);
}
tot++;
memset(c,0xcf,sizeof(c));
memset(ans,INF,sizeof(ans));
cdq(1,m);//二分范围[1,m]
for(int i=n+1;i<=m;i++){
if(a[i].op==2){
cout<<ans[i]<<endl;
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
另外，这里附上CDQ分治的另外两道例题（洛谷 P3810 P4390）
基于值域的整体二分
例题
POJ2104 K-th Number
这是一道模板题，可以用四种方法AC。
这里介绍树状数组实现的整体二分做法。
将询问序列作为三元组表示
中
小的数。设solve(L,R,1,t)表示值域为[L,R]的序列，对询问序列1~t作出回答。
步骤如下：
1 mid=L+R>>1
2 利用树状数组，对于当前询问序列，统计数字序列在中小于等于mid的数有多少个，记为
。
3 若，则将询问加入序列lq中，否则令
，将询问加入序列rq中。
4 将lq和rq拷贝回原来的数组
5 还原树状数组
6 递归solve(L,mid,1,?)和solve(mid+1,R,?+1,t)
递归边界：L=R时，将L作为目前询问序列中所有询问的答案。
未离散化时间复杂度：（SIZE为值域大小）。
离散化时间复杂度：。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const int INF=0x3f3f3f3f;
struct node{
int id,x,y,z;
}q[maxn],lq[maxn],rq[maxn];
int n,m,t=0,c[maxn],ans[maxn];
void add(int x,int y){
for(int i=x;i<=n;i+=i&-i) c[i]+=y;
}
int ask(int x){
int sum=0;
for(int i=x;i>=1;i-=i&-i) sum+=c[i];
return sum;
}
void solve(int lval,int rval,int st,int ed){
if(st>ed) return;
if(lval==rval){
for(int i=st;i<=ed;i++){
if(q[i].id>0) ans[q[i].id]=lval;
}
return;
}
int mid=lval+rval>>1;
int lt=0,rt=0;
for(int i=st;i<=ed;i++){
if(q[i].id==0){
if(q[i].y<=mid) add(q[i].x,1),lq[++lt]=q[i];
else rq[++rt]=q[i];
}
else{
int cnt=ask(q[i].y)-ask(q[i].x-1);
if(cnt>=q[i].z) lq[++lt]=q[i];
else q[i].z-=cnt,rq[++rt]=q[i];
}
}
for(int i=st;i<=ed;i++){
if(q[i].id==0&&q[i].y<=mid) add(q[i].x,-1);
}
for(int i=1;i<=lt;i++) q[st+i-1]=lq[i];
for(int i=1;i<=rt;i++) q[st+lt+i-1]=rq[i];
solve(lval,mid,st,st+lt-1);
solve(mid+1,rval,st+lt,ed);
}
int main() {
ios::sync_with_stdio(false);
// freopen("K-th Number.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++){
q[++t].id=0;
q[t].x=i;
cin>>q[t].y;
}
for(int i=1;i<=m;i++){
q[++t].id=i;
cin>>q[t].x>>q[t].y>>q[t].z;
}
solve(-INF,INF,1,t);
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
另外，若序列存在带修改操作（如A[x]=y)，那么做如下转化：
将这个操作转化为在x位置去掉一个值为A[x]的数（记该类操作为-1），增加一个值为y的数（记该类操作为0）两次操作。然后将所有操作包括询问进行整体二分即可。（例题 BZOJ 1901/ZOJ 2112）
网友评论