模板：ＫｄＴｒｅｅ

mac2022-06-30 141

ＫｄＴｒｅｅ模板ｃｏｄｅ：

#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const int maxn=1e6+500; const int inf=1e9+7; int n,m; int nowD,rt,ql,qr,ans; /*==================Define Area================*/ namespace KD_Tree { struct node { int Mn[2],Mx[2]; int d[2]; int l,r; void init() { Mn[0]=Mx[0]=d[0]; Mn[1]=Mx[1]=d[1]; } void Init(int x,int y) { Mn[0]=Mx[0]=d[0]=x; Mn[1]=Mx[1]=d[1]=y; } }t[maxn<<1]; bool cmp(node a,node b) { return a.d[nowD]!=b.d[nowD]?a.d[nowD]<b.d[nowD]:a.d[!nowD]<b.d[!nowD]; } void update(int o) { if(t[o].l) { t[o].Mx[0]=max(t[o].Mx[0],t[t[o].l].Mx[0]); t[o].Mx[1]=max(t[o].Mx[1],t[t[o].l].Mx[1]); t[o].Mn[0]=min(t[o].Mn[0],t[t[o].l].Mn[0]); t[o].Mn[1]=min(t[o].Mn[1],t[t[o].l].Mn[1]); } if(t[o].r) { t[o].Mx[0]=max(t[o].Mx[0],t[t[o].r].Mx[0]); t[o].Mx[1]=max(t[o].Mx[1],t[t[o].r].Mx[1]); t[o].Mn[0]=min(t[o].Mn[0],t[t[o].r].Mn[0]); t[o].Mn[1]=min(t[o].Mn[1],t[t[o].r].Mn[1]); } } int Build(int l,int r,int D) { int mid=(l+r)>>1; nowD=D; nth_element(t+l,t+mid,t+r+1,cmp); if(l!=mid) t[mid].l=Build(l,mid-1,!D); if(r!=mid) t[mid].r=Build(mid+1,r,!D); t[mid].init(); update(mid); return mid; } int dist(int o) { int dis=0; if(ql<t[o].Mn[0]) dis+=t[o].Mn[0]-ql; if(ql>t[o].Mx[0]) dis+=ql-t[o].Mx[0]; if(qr<t[o].Mn[1]) dis+=t[o].Mn[1]-qr; if(qr>t[o].Mx[1]) dis+=qr-t[o].Mx[1]; return dis; } void Query(int o) { int dl,dr,d0; d0=abs(t[o].d[0]-ql)+abs(t[o].d[1]-qr); if(d0<ans) ans=d0; if(t[o].l) dl=dist(t[o].l); else dl=inf; if(t[o].r) dr=dist(t[o].r); else dr=inf; if(dl<dr) { if(dl<ans) Query(t[o].l); if(dr<ans) Query(t[o].r); } else { if(dr<ans) Query(t[o].r); if(dl<ans) Query(t[o].l); } } void Insert(int o) { int p=rt,D=0; while(1) { t[p].Mx[0]=max(t[p].Mx[0],t[o].Mx[0]); t[p].Mx[1]=max(t[p].Mx[1],t[o].Mx[1]); t[p].Mn[0]=min(t[p].Mn[0],t[o].Mn[0]); t[p].Mn[1]=min(t[p].Mn[1],t[o].Mn[1]); if(t[o].d[D]>=t[p].d[D]) { if(!t[p].r) { t[p].r=o; return ; } else p=t[p].r; } else { if(!t[p].l) { t[p].l=o; return ; } else p=t[p].l; } D=!D; } } }; using namespace KD_Tree; int main() { read(n);read(m); for(int i=1;i<=n;i++) { read(t[i].d[0]);read(t[i].d[1]); } rt=Build(1,n,0); // printf("%d\n",rt); // puts(""); int opt,x,y; for(int i=1;i<=m;i++) { read(opt);read(x);read(y); if(opt==1) { ++n; t[n].Init(x,y); Insert(n); } else { ans=inf; ql=x,qr=y; Query(rt); printf("%d\n",ans); } } return 0; }

转载于:https://www.cnblogs.com/Apocrypha/p/9430736.html