最详细 CDQ 分治题解

这是一道二维平面的数点，同时也加上了时间。做过动态逆序对的可能会记得对于 k 维平面、动态加点和询问的题目，可以将时间也当作一个维度，计算 x 轴、 y 轴、时间都更小的点。由于二维平面不可能所有点都在当前点的左下角，所以我们将图掉转做4次 CDQ, 因为是曼哈顿距离，所以用树状数组维护 x+y 的最大值，用询问点的 x+y 减去最大的 x+y 即可，掉转需要计算最大 x 值和 y 值，注意最后要 +1 因为掉转时 x/y 最大的那个点如果掉成 0 树状数组会爆。输入也要+1因为坐标最小为0. 以下是代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,tree[1000005],lx,ly,ans[600005];
struct xyl{int x,y,id;bool op;}a[600005],k[600005],tmp[600005];
void add(int x,int d){for(;x<=ly;x+=x&-x)tree[x]=max(tree[x],d);}
void clr(int x){for(;x<=ly&&tree[x];x+=x&-x)tree[x]=0;}
int qry(int x){int res=0;for(;x;x^=x&-x)res=max(tree[x],res);return res;}
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1,cnt=0;
    cdq(l,mid),cdq(mid+1,r);
    for(;cnt2<=r;++cnt2){
        for(;cnt1<=mid&&a[cnt1].x<=a[cnt2].x;++cnt1){if(!a[cnt1].op)add(a[cnt1].y,a[cnt1].x+a[cnt1].y);k[++cnt]=a[cnt1];}
        int t=qry(a[cnt2].y);if(a[cnt2].op&&t)ans[a[cnt2].id]=min(ans[a[cnt2].id],a[cnt2].x+a[cnt2].y-t);k[++cnt]=a[cnt2];
    }
    for(;cnt1<=mid;++cnt1)k[++cnt]=a[cnt1];
    for(int i=l;i<=mid;++i)if(!a[i].op)clr(a[i].y);
    for(int i=l;i<=r;++i)a[i]=k[i-l+1];
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]={read()+1,read()+1,0,0},tmp[i]=a[i],lx=max(lx,tmp[i].x+1),ly=max(ly,tmp[i].y+1);
    for(int i=1,od;i<=m;++i)od=read()-1,a[n+i]={read()+1,read()+1,i,od},tmp[n+i]=a[n+i],lx=max(lx,tmp[n+i].x+1),ly=max(ly,tmp[n+i].y+1);
    memset(ans,127,sizeof ans);
    cdq(1,n+m);
    for(int i=1;i<=n+m;++i)a[i]=tmp[i],a[i].x=lx-tmp[i].x;
    cdq(1,n+m);
    for(int i=1;i<=n+m;++i)a[i]=tmp[i],a[i].y=ly-tmp[i].y;
    cdq(1,n+m);
    for(int i=1;i<=n+m;++i)a[i]=tmp[i],a[i].x=lx-tmp[i].x,a[i].y=ly-tmp[i].y;
    cdq(1,n+m);
    for(int i=1;i<=m;++i)if(tmp[n+i].op)write(ans[i]),putchar_unlocked('\n');
    return 0;
}