1 条题解

  • 0
    @ 2025-8-24 22:18:43

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar wishapig
    最黑的那段路，终究是要自己走完的

    搬运于2025-08-24 22:18:43，当前版本为作者最后更新于2020-05-04 14:22:55，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    关于KDT最近邻查询方面，前几个星期被

    https://www.luogu.com.cn/user/48843
    /www.luogu.com.cn/user/35760)两位巨佬给D得体无完肤（导致现在我看到最近邻就头疼）

    具体可见

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

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

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

    首先有

    max⁡i{∣xi−x∣+∣yi−y∣}\max_i\{|x_i-x|+|y_i-y|\} =max⁡i{max⁡(xi−x,x−xi),max⁡(yi−y,y−yi)}=\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{∣xi−x∣+∣yi−y∣}\min_i\{|x_i-x|+|y_i-y|\}

    这把xx与xix_i，yy与yiy_i的大小关系分4部分分别查询即可

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

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

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

    #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最近邻查询最坏到底是多少的？有没有卡到极限的方法？各位巨佬可以私信我（我到现在都没弄明白）

    • 1

    [BJWC2014] 数据

    信息

    ID
    5251
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 30ms