KD_Tree 【bzoj2648 bzoj2716】SJY摆棋子 [voilet 3] 天使玩偶

本文主要是介绍KD_Tree 【bzoj2648 bzoj2716】SJY摆棋子 [voilet 3] 天使玩偶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
维护一堆点，支持插入一个点和查询距离一个给定的点的曼哈顿距离最近的点。

题目分析:(KD_Tree)
据说还可以用CDQ分治做，但是因为要分四个象限讨论，很麻烦的说呀QAQ
我这种萌萌哒蒟蒻自然去学KDT啦~(>▽<)~

KD_Tree 主要应用于解决多维空间内一堆点的问题。
这道题只要正常建树并且插入就可以了。
查询的时候相当于爆搜+剪枝，每搜到一个点都写给两个儿子写一个估价函数，然后判断搜索的先后顺序什么的（真不知道这种东西的时间复杂度是怎么保证的，玄学╮(╯_╰)╭）。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define M 500500
using namespace std;
const int INF=0x3f3f3f3f;
struct point{int x,y;point(int x=0,int y=0):x(x),y(y){}int operator | (const point &c) const { return abs(x-c.x)+abs(y-c.y); }
}p[M];
bool cmpx(const point &a,const point &b) { return a.x<b.x; }
bool cmpy(const point &a,const point &b) { return a.y<b.y; }
inline point Min(point a,point b) { return point(min(a.x,b.x),min(a.y,b.y)); }
inline point Max(point a,point b) { return point(max(a.x,b.x),max(a.y,b.y)); }
namespace K_Dimensional_Tree{struct KDT{KDT *ch[2];point val,S,T;KDT(point _):val(_){ch[0]=ch[1]=0x0;S=T=val;}void maintain(){if(ch[0]){S=Min(S,ch[0]->S);T=Max(T,ch[0]->T);}if(ch[1]){S=Min(S,ch[1]->S);T=Max(T,ch[1]->T);}}int dir(const point &p){int re=0;if(p.x<S.x) re+=S.x-p.x;if(p.x>T.x) re+=p.x-T.x;if(p.y<S.y) re+=S.y-p.y;if(p.y>T.y) re+=p.y-T.y;return re;}}*root;void build_tree(KDT *&c,int l,int r,bool flag){if(l>r) return;int mid=l+r>>1;nth_element(p+l,p+mid,p+r+1,flag?cmpy:cmpx);c=new KDT(p[mid]);build_tree(c->ch[0],l,mid-1,!flag);build_tree(c->ch[1],mid+1,r,!flag);c->maintain();}void insert(KDT *&c,const point &x,bool flag){if(!c) { c=new KDT(x); return; }int d=(flag?cmpy:cmpx)(c->val,x);insert(c->ch[d],x,!flag);c->maintain();}void query(KDT *c,const point &x,int &ans){ans=min(ans,x|c->val);int dis[2],d1=0,d2=1;dis[0]=c->ch[0]?c->ch[0]->dir(x):INF;dis[1]=c->ch[1]?c->ch[1]->dir(x):INF;if(dis[0]>dis[1]) d1=1,d2=0;if(c->ch[d1] && dis[d1]<ans) query(c->ch[d1],x,ans);if(c->ch[d2] && dis[d2]<ans) query(c->ch[d2],x,ans);}}
int main()
{using namespace K_Dimensional_Tree;int n,m,opt;point a;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);build_tree(root,1,n,false);for(int i=1;i<=m;i++){scanf("%d%d%d",&opt,&a.x,&a.y);if(opt==1) insert(root,a,false);else{int ans=INF;query(root,a,ans);printf("%d\n",ans);}}return 0;
}