【BZOJ2648】SJY摆棋子

题目大意：维护一个二维平面，平面上初始有 N 个点，支持两种操作：平面加点、查询距离某个指定点的最小哈密顿距离。

题解：学习到了 kd-tree 数据结构。

kd-tree 类似于平衡树，即：每个节点都维护了一个点坐标的信息和一个矩形区间的边界，与线段树的 leafy tree 性质不同。不过，由于 kd-tree 不涉及旋转以及维护的矩形区域的分割特征，可以使用 pushup 操作进行上传边界信息。kd-tree 的查询优化算法核心思想基于估价函数的设计，估价函数一般是某一个区域的最优解，即：若某个区域的最优解都不能对答案产生影响，那么直接忽略这块区域即可，这样就可以使得时间复杂度降低，从而达到优化的目的。时间复杂度为 \(O(\sqrt(n))\)，目前不会证明。。

update at 2019.3.17

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=3e5+10;

const int inf=0x3f3f3f3f;

const double alpha=0.75;

inline int read(){

	int x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

int n,m;

struct node{

	#define ls(x) t[x].ch[0]

	#define rs(x) t[x].ch[1]

	int p[2],x[2],y[2],ch[2],size;

}t[maxn<<1];

int root,d,ans,id[maxn],tot;

inline bool cmp(int x,int y){return t[x].p[d]<t[y].p[d];}

inline int getdis(int o,int x,int y){

	return max(t[o].x[0]-x,0)+max(x-t[o].x[1],0)+max(t[o].y[0]-y,0)+max(y-t[o].y[1],0);

}

inline void pushup(int o){

	t[o].x[0]=min(min(t[ls(o)].x[0],t[rs(o)].x[0]),t[o].p[0]);

	t[o].x[1]=max(max(t[ls(o)].x[1],t[rs(o)].x[1]),t[o].p[0]);

	t[o].y[0]=min(min(t[ls(o)].y[0],t[rs(o)].y[0]),t[o].p[1]);

	t[o].y[1]=max(max(t[ls(o)].y[1],t[rs(o)].y[1]),t[o].p[1]);

	t[o].size=t[ls(o)].size+t[rs(o)].size+1;

}

int build(int l,int r,int now){

	if(l>r)return 0;

	int mid=l+r>>1;

	d=now,nth_element(id+l,id+mid,id+r+1,cmp);

	ls(id[mid])=build(l,mid-1,now^1),rs(id[mid])=build(mid+1,r,now^1);

	return pushup(id[mid]),id[mid];

}

inline bool isbad(int o){return (double)max(t[ls(o)].size,t[rs(o)].size)>alpha*t[o].size;}

void dfs(int o){if(o)dfs(ls(o)),id[++tot]=o,dfs(rs(o));}

void insert(int &o,int p[2],int now){

	if(!o){

		o=++n,t[o].p[0]=p[0],t[o].p[1]=p[1],pushup(o);

		return;

	}

	else if(t[o].p[now]<=p[now])insert(rs(o),p,now^1);

	else insert(ls(o),p,now^1);

	pushup(o);

	if(isbad(o))tot=0,dfs(o),o=build(1,tot,now);

}

void query(int o,int x,int y){

	int dn=abs(x-t[o].p[0])+abs(y-t[o].p[1]),dl,dr;

	ans=min(ans,dn);

	dl=ls(o)?getdis(ls(o),x,y):inf;

	dr=rs(o)?getdis(rs(o),x,y):inf;

	if(dl<dr){

		if(dl<ans)query(ls(o),x,y);

		if(dr<ans)query(rs(o),x,y);

	}else{

		if(dr<ans)query(rs(o),x,y);

		if(dl<ans)query(ls(o),x,y);

	}

}

void read_and_parse(){

	t[0].x[0]=t[0].y[0]=inf,t[0].x[1]=t[0].y[1]=-inf;

	n=read(),m=read();

	for(int i=1;i<=n;i++)t[i].p[0]=read(),t[i].p[1]=read(),id[++tot]=i;

	root=build(1,n,0);

}

void solve(){

	int p[2];

	while(m--){

		int opt=read(),x=read(),y=read();

		if(opt==1)p[0]=x,p[1]=y,insert(root,p,0);

		else ans=inf,query(root,x,y),printf("%d\n",ans);

	}

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【BZOJ2648】SJY摆棋子

最新文章

热门文章