bzoj 2648 SJY摆棋子——KDtree

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2648

第一道KDtree!

学习资料：https://blog.csdn.net/zhl30041839/article/details/9277807

　　　　　https://www.cnblogs.com/galaxies/p/kdtree.html

这道题的代码是学习(抄)的这里的：https://blog.csdn.net/lych_cys/article/details/50809141

#include
#include
#include
#include
using namespace std;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,fx,rt,ans,tot;
struct Node{int x[2],y[2],p[2];//x:min y:max p:ps
}a[N>>1];
bool cmp(Node u,Node v){return u.p[fx]<v.p[fx];}
struct Kd{int c[N][2];Node s[N],q;//大家的儿子、根和唯一的询问void add(int cr,Node k){    for(int i=0;i<2;i++) s[cr].x[i]=s[cr].y[i]=s[cr].p[i]=k.p[i];}void pshp(int cr){int ls=c[cr][0],rs=c[cr][1];for(int i=0;i<2;i++){if(ls)s[cr].x[i]=min(s[cr].x[i],s[ls].x[i]),s[cr].y[i]=max(s[cr].y[i],s[ls].y[i]);if(rs)s[cr].x[i]=min(s[cr].x[i],s[rs].x[i]),s[cr].y[i]=max(s[cr].y[i],s[rs].y[i]);}}void build(int &cr,int l,int r,int now){int mid=l+r>>1;fx=now;nth_element(a+l,a+mid,a+r+1,cmp);
//        cr=mid;add(cr,a[mid]);//cr=mid!cr=++tot;add(cr,a[mid]);if(l0],l,mid-1,!now);///if()if(mid1],mid+1,r,!now);pshp(cr);}void insert(int &cr,int now){
//        if(!cr){cr=++n;add(cr,q);return;}//cr=++n!if(!cr){cr=++tot;add(cr,q);return;}if(q.p[now]0],!now);else insert(c[cr][1],!now);pshp(cr);}int dist(int cr,Node k)//在区域内返回0 
    {int ret=0;for(int i=0;i<2;i++)ret+=max(0,s[cr].x[i]-k.p[i])+max(0,k.p[i]-s[cr].y[i]);return ret;}void query(int cr,int now){ans=min(ans,abs(s[cr].p[0]-q.p[0])+abs(s[cr].p[1]-q.p[1]));int dl=c[cr][0]?dist(c[cr][0],q):INF,dr=c[cr][1]?dist(c[cr][1],q):INF;if(dl<dr){ if(dl0],!now); if(dr1],!now);}else{ if(dr1],!now); if(dl0],!now);}}
}kd;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&a[i].p[0],&a[i].p[1]);kd.build(rt,1,n,0);for(int i=1,op;i<=m;i++){scanf("%d%d%d",&op,&kd.q.p[0],&kd.q.p[1]);if(op==1) kd.insert(rt,0);else {    ans=INF; kd.query(rt,0); printf("%d\n",ans);}}return 0;
}

转载于:https://www.cnblogs.com/Narh/p/9490321.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！