CDQ分治学习笔记

  • 2020 年 8 月 22 日
  • 筆記

CDQ分治是2008 IOI金牌神仙陈丹琦在国家集训队引入的一种离线分治算法，

对时间分治，时间复杂度为O(logn*单次处理复杂度）。

思路大体是这样的：

数据结构问题的操作通常可以分为修改和查询两类，而每一次查询就是询问前面所有的修改对当前的影响，

而CDQ分治将动态的问题分解为一个个静态的，对时间点计算影响的问题，并用分治的方法统一求解。

当前有N个操作，我们用solve(l,r)计算在[l,r]区间内的修改对区间内查询的贡献，做法如下：

　　设mid=(l+r)/2，

　　1.分治计算solve(l,mid)

　　2.分治计算solve(mid+1,r)

　　3.计算[l,mid]内所有的修改对[mid+1,r]的查询的影响

solve(1,N)是调用入口，当l==r时，只有一项操作，可以直接返回。

我们将原来的动态问题分解成了一个个步骤3的静态问题，其数量是(1+2+4+…+2^k)=O(N)个，其中2^k<=N。

而每一个原来的询问由O(logN)个静态问题组成，由于总共递归O(logN)层，所以复杂度是O(logn*单次处理复杂度）。

因为每一个静态问题的时复只与当前的l，r有关，因此效率较高。

 

例题 天使的玩偶//www.luogu.com.cn/problem/P4169

对于每个查询，要计算min{|x-xi|+|y-yi|}，为了去掉绝对值符号，我们将询问分成四瓣，分别查询当前点左下、左上、右下、右上的最近距离。

将其分解成

　　x+y-max{xi+yi}

　　x-y-max{xi-yi}

　　-x+y-max{-xi+yi}

　　-x-y-max{-xi-yi}

在计算步骤3时，枚举四个方向，并用树状数组维护最大值即可，

实现细节看代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAX 300010
#define Inf 1000001
#define lowbit(x) x&-x
#define PII pair<int,int>
#define mk make_pair
#define ft first
#define sc second
using namespace std;
struct pos{
    int x,y;
    int type,ans;
}p[MAX*2];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int t[Inf],cnt,q[MAX*2];
PII opt[MAX*2];
void update(int x,int k){
    for(;x<=Inf&&t[x]<k;x+=lowbit(x))t[x]=k;
}
int get(int x){
    int res=0x80808080;
    for(;x;x-=lowbit(x))res=max(res,t[x]);
    return res;
}
void del(int x){
    for(;x<=Inf;x+=lowbit(x))t[x]=0x80808080;
}
int type(int x,int y,int id){
    switch(id){
        case 0:return x+y;
        case 1:return x-y;
        case 2:return -x+y;
        case 3:return -x-y;
    }
}
bool cmp(int a,int b){return p[a].x<p[b].x;}
void work(int l,int r){
    int mid=(l+r)/2,x,y;
    int num;
    cnt=0;
    for(int i=l;i<=mid;i++)
        if(!p[i].type)q[cnt++]=i;
    for(int i=mid+1;i<=r;i++)
        if(p[i].type)q[cnt++]=i;
    sort(q,q+cnt,cmp);
    for(int id=0;id<4;id++){
        num=-1;
        for(int i=(id<2?0:cnt-1);(id<2?i<cnt:i>=0);i+=(id<2?1:-1)){
            x=p[q[i]].x,y=p[q[i]].y;
            if(!p[q[i]].type){
                opt[++num]=mk(id&1?Inf-y:y,type(x,y,id));
                update(opt[num].ft,opt[num].sc);
            }
            else{
                if(num==-1)continue;
                p[q[i]].ans=min(p[q[i]].ans,type(x,y,id)-get(id&1?Inf-y:y));
            }
        }
        for(int i=0;i<=num;i++){
            del(opt[i].ft);
        }
    }
}
void cdq(int left,int right){
    if(left==right)return;
    int mid=(left+right)/2;
    cdq(left,mid); cdq(mid+1,right);
    work(left,right);
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n+m;i++){
        if(i>=n)p[i].type=read()-1;
        else p[i].type=0;
        p[i].x=read(),p[i].y=read();
        p[i].ans=2*Inf;
    }
    memset(t,0x80,sizeof(t));
    cdq(0,n+m-1);
    for(int i=0;i<n+m;i++){
        if(p[i].type)printf("%d\n",p[i].ans);
    }
    return 0;
}

其中0x80808080是极小值

VirMach 便宜 VPS

QNews

QNews