题解 P6224 【[BJWC2014]数据】

· · 题解

关于KDT最近邻查询方面，前几个星期被@Tweetuski和@142857cs两位巨佬给D得体无完肤（导致现在我看到最近邻就头疼）

具体可见

https://www.luogu.com.cn/discuss/show/214220

https://www.luogu.com.cn/discuss/show/214426

基于对最近邻查询深深的恐惧感，这题我一开始没有用最近邻

首先有

\max_i\{|x_i-x|+|y_i-y|\} =\max_i\{\max(x_i-x,x-x_i),\max(y_i-y,y-y_i)\} =\max_i\{x_i-x+y_i-y,x_i-x+y-y_i,x-x_i+y_i-y,x-x_i+y-y_i\}

那维护\max\{x_i+y_i\},\max\{x_i-y_i\},\max\{-x_i+y_i\},\max\{-x_i-y_i\},就可以了

然后

\min_i\{|x_i-x|+|y_i-y|\}

这把x与x_i，y与y_i的大小关系分4部分分别查询即可

在类似替罪羊树的重构方面，我也被@142857cs给D了，所以我预先把所有点都记下来，提前建好树形，避免了重构的操作

所以这种方法没用最近邻查询，复杂度是标准的O(n\sqrt{n})，带4倍常数（但是出题人很善良的把根号卡掉了）

这是根号的代码，也许有大佬可以帮我卡卡？

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pair;
const int N=4e5+5;
const Pair Em=make_pair(-1e9,-1e9);
#define F first
#define S second
int L[N],R[N],U[N],D[N],ls[N],rs[N],loc[N],fa[N];
int n,q,treesize,rt,cnt,maxx,maxy,Dir,l,r,d,u,k;
Pair poi[N];
bool exi[N];
struct Point{ int x,y,loc; bool E; } p[N];
struct Ques{ int op,x,y,loc; } que[N];
struct Data{ int a[4]; } Da,dat[N];
Data operator + (const Data& a, const Data& b){
    Data c;
    c.a[0]=min(a.a[0],b.a[0]); c.a[1]=min(a.a[1],b.a[1]);
    c.a[2]=min(a.a[2],b.a[2]); c.a[3]=min(a.a[3],b.a[3]);
    return c;
}
bool operator < (const Point& a, const Point& b){ return Dir?a.y<b.y:a.x<b.x; }
inline void Mix(Data& D, Pair P){
    if (P.F==Em.F && P.S==Em.S) D.a[0]=D.a[1]=D.a[2]=D.a[3]=2e9;
    else {
        int x=P.F,y=P.S;
        D.a[0]=-x-y; D.a[1]=-x+y;
        D.a[2]= x-y; D.a[3]= x+y;
    }
}
inline void Newnode(int now){
    if (!exi[now]) L[now]=U[now]=1e9,R[now]=D[now]=0,Mix(dat[now],Em); else
    L[now]=R[now]=poi[now].F,U[now]=D[now]=poi[now].S,Mix(dat[now],poi[now]);
}
inline void pushup(int now){
    Newnode(now);
    L[now]=min(L[now],min(L[ls[now]],L[rs[now]]));
    U[now]=min(U[now],min(U[ls[now]],U[rs[now]]));
    R[now]=max(R[now],max(R[ls[now]],R[rs[now]]));
    D[now]=max(D[now],max(D[ls[now]],D[rs[now]]));
    dat[now]=dat[now]+dat[ls[now]]+dat[rs[now]];
}
void build(int& now, int l, int r, int tag){
    if (l>r) return;
    int mid=(l+r)>>1; now=++treesize; Dir=tag;
    nth_element(p+l,p+mid,p+r+1);
    poi[now]=make_pair(p[mid].x,p[mid].y); exi[now]=p[mid].E;
    Newnode(now);
    if (p[mid].loc) loc[p[mid].loc]=now;
    build(ls[now],l,mid-1,tag^1); build(rs[now],mid+1,r,tag^1);
    if (ls[now]) fa[ls[now]]=now;
    if (rs[now]) fa[rs[now]]=now;
    pushup(now);
}
int query(int now){
    if (!now) return 2e9;
    if (l<=L[now] && R[now]<=r && u<=U[now] && D[now]<=d) return dat[now].a[k];
    if (l>R[now] || r<L[now] || u>D[now] || d<U[now]) return 2e9;
    int x=poi[now].F,y=poi[now].S,c=2e9;
    if (l<=x && x<=r && u<=y && y<=d && exi[now]){
        if (k==0) c=-x-y;
        else if (k==1) c=-x+y;
        else if (k==2) c= x-y;
        else c=x+y;
    }
    return min(c,min(query(ls[now]),query(rs[now])));
}
inline int read(){
    int num=0,fu=1; char ch=getchar();
    while (ch<'0' || ch>'9') fu&=(ch!='-'),ch=getchar();
    while (ch>='0' && ch<='9') num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return fu?num:-num;
}
int main(){
    n=read(); Newnode(0); Da.a[0]=Da.a[1]=Da.a[2]=Da.a[3]=-2e9;
    for (int i=1; i<=n; i++){
        p[i].x=read(),p[i].y=read(),p[i].E=1;
        Da.a[0]=max(Da.a[0],-p[i].x-p[i].y); Da.a[1]=max(Da.a[1],-p[i].x+p[i].y);
        Da.a[2]=max(Da.a[2], p[i].x-p[i].y); Da.a[3]=max(Da.a[3], p[i].x+p[i].y);
        maxx=max(maxx,p[i].x); maxy=max(maxy,p[i].y);
    }
    q=read(); cnt=n;
    for (int i=1; i<=q; i++){
        que[i].op=read(); que[i].x=read(); que[i].y=read();
        if (!que[i].op){
            cnt++,p[cnt].x=que[i].x,p[cnt].y=que[i].y,p[cnt].loc=que[i].loc=cnt;
            maxx=max(maxx,p[cnt].x); maxy=max(maxy,p[cnt].y);
        }
    }
    build(rt,1,cnt,0);
    for (int i=1; i<=q; i++){
        int x=que[i].x,y=que[i].y;
        if (que[i].op==0){
            int u=loc[que[i].loc]; exi[u]=1; Newnode(u);
            Da.a[0]=max(Da.a[0],-x-y); Da.a[1]=max(Da.a[1],-x+y);
            Da.a[2]=max(Da.a[2], x-y); Da.a[3]=max(Da.a[3], x+y);
            for (; u; u=fa[u]) pushup(u);
        } else
        if (que[i].op==1){
            int ans=2e9,r1,r2,r3,r4;
            l=0,r=x,u=0,d=y,k=0; r1=query(rt);
            l=0,r=x,u=y,d=maxy,k=1; r2=query(rt);
            l=x,r=maxx,u=0,d=y,k=2; r3=query(rt);
            l=x,r=maxx,u=y,d=maxy,k=3; r4=query(rt);
            if (r1!=2e9) ans=min(ans,r1+x+y);
            if (r2!=2e9) ans=min(ans,r2+x-y);
            if (r3!=2e9) ans=min(ans,r3-x+y);
            if (r4!=2e9) ans=min(ans,r4-x-y);
            printf("%d\n",ans);
        } else printf("%d\n",max(max(x+y+Da.a[0],x-y+Da.a[1]),max(-x+y+Da.a[2],-x-y+Da.a[3])));
    }
    return 0;
}

无奈，上面这份代码卡不过去，所以我又写了一份最近邻查询的版本，下面是代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define F first
#define S second
int L[N],R[N],U[N],D[N],ls[N],rs[N],loc[N],fa[N],Px[N],Py[N];
int n,q,treesize,rt,cnt,maxx,maxy,Dir,l,r,d,u,k,x,y,ans;
bool exi[N];
struct Point{ int x,y,loc; bool E; } p[N];
struct Ques{ int op,x,y,loc; } que[N];
struct Data{ int a[4]; } Da;
bool operator < (const Point& a, const Point& b){ return Dir?a.y<b.y:a.x<b.x; }
inline void Newnode(int now){
    if (!exi[now]) L[now]=U[now]=1e9,R[now]=D[now]=0; else
    L[now]=R[now]=Px[now],U[now]=D[now]=Py[now];
}
inline void pushup(int now){
    Newnode(now);
    L[now]=min(L[now],min(L[ls[now]],L[rs[now]]));
    U[now]=min(U[now],min(U[ls[now]],U[rs[now]]));
    R[now]=max(R[now],max(R[ls[now]],R[rs[now]]));
    D[now]=max(D[now],max(D[ls[now]],D[rs[now]]));
}
void build(int& now, int l, int r, int tag){
    if (l>r) return;
    int mid=(l+r)>>1; now=++treesize; Dir=tag;
    nth_element(p+l,p+mid,p+r+1);
    Px[now]=p[mid].x; Py[now]=p[mid].y; exi[now]=p[mid].E;
    Newnode(now);
    if (p[mid].loc) loc[p[mid].loc]=now;
    build(ls[now],l,mid-1,tag^1); build(rs[now],mid+1,r,tag^1);
    if (ls[now]) fa[ls[now]]=now;
    if (rs[now]) fa[rs[now]]=now;
    pushup(now);
}
inline int read(){
    int num=0,fu=1; char ch=getchar();
    while (ch<'0' || ch>'9') fu&=(ch!='-'),ch=getchar();
    while (ch>='0' && ch<='9') num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return fu?num:-num;
}
inline int Get_dis(int now){
    if (!now) return 2e9;
    int ans=0;
    if (x<L[now]) ans+=L[now]-x;
    if (y<U[now]) ans+=U[now]-y;
    if (x>R[now]) ans+=x-R[now];
    if (y>D[now]) ans+=y-D[now];
    return ans;
}
void query(int now){
    if (!now) return;
    if (exi[now]) ans=min(ans,abs(Px[now]-x)+abs(Py[now]-y));
    int dl=Get_dis(ls[now]),dr=Get_dis(rs[now]);
    if (dl<dr){
        if (dl<ans) query(ls[now]);
        if (dr<ans) query(rs[now]);
    } else {
        if (dr<ans) query(rs[now]);
        if (dl<ans) query(ls[now]);
    }
}
int main(){
    n=read(); Newnode(0); Da.a[0]=Da.a[1]=Da.a[2]=Da.a[3]=-2e9;
    for (int i=1; i<=n; i++){
        p[i].x=read(),p[i].y=read(),p[i].E=1;
        Da.a[0]=max(Da.a[0],-p[i].x-p[i].y); Da.a[1]=max(Da.a[1],-p[i].x+p[i].y);
        Da.a[2]=max(Da.a[2], p[i].x-p[i].y); Da.a[3]=max(Da.a[3], p[i].x+p[i].y);
        maxx=max(maxx,p[i].x); maxy=max(maxy,p[i].y);
    }
    q=read(); cnt=n;
    for (int i=1; i<=q; i++){
        que[i].op=read(); que[i].x=read(); que[i].y=read();
        if (!que[i].op){
            cnt++,p[cnt].x=que[i].x,p[cnt].y=que[i].y,p[cnt].loc=que[i].loc=cnt;
            maxx=max(maxx,p[cnt].x); maxy=max(maxy,p[cnt].y);
        }
    }
    build(rt,1,cnt,0);
    for (int i=1; i<=q; i++){
        x=que[i].x,y=que[i].y;
        if (que[i].op==0){
            int u=loc[que[i].loc]; exi[u]=1; Newnode(u);
            Da.a[0]=max(Da.a[0],-x-y); Da.a[1]=max(Da.a[1],-x+y);
            Da.a[2]=max(Da.a[2], x-y); Da.a[3]=max(Da.a[3], x+y);
            for (; u; u=fa[u]) pushup(u);
        } else
        if (que[i].op==1){
            ans=2e9; query(rt);
            printf("%d\n",ans);
        } else printf("%d\n",max(max(x+y+Da.a[0],x-y+Da.a[1]),max(-x+y+Da.a[2],-x-y+Da.a[3])));
    }
    return 0;
}

最后，我还是要问：KDT最近邻查询最坏到底是多少的？有没有卡到极限的方法？各位巨佬可以私信我（我到现在都没弄明白）