BZOJ 2716/2648
HJWJBSR
posted @ 2015年9月15日 21:37
in 题解
, 664 阅读
膜了一发K-D Tree这种高端东西
感觉比想象中好写。
但是不用指针就会T,用了指针就跑的飞起只有10+s感觉实在不科学= =
这个版本并没有套上暴力重建,也懒得套暴力重建了= =
#include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> using namespace std; #define N 1000050 #define INF 0x7f7f7f7f struct Point {int x,y,x1,y1,x2,y2;Point *c[2];}; int n,m; bool cmp(const Point &x,const Point &y) {return x.x<y.x;} bool cpm(const Point &x,const Point &y) {return x.y<y.y;} inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; } struct KD_Tree { int st,ans;Point now,*gf,t[N]; inline int Minimum(Point *x,Point y) { int k=0; if (y.x<x->x1) k+=x->x1-y.x;else if (y.x>x->x2) k+=y.x-x->x2; if (y.y<x->y1) k+=x->y1-y.y;else if (y.y>x->y2) k+=y.y-x->y2; return k; } inline int Dis(Point *x,Point y) {return abs(x->x-y.x)+abs(x->y-y.y);} inline void Get(int x) { t[x].x=t[x].x1=t[x].x2=Read(); t[x].y=t[x].y1=t[x].y2=Read(); } inline void Update(Point *x,Point *y) { x->x1=min(x->x1,y->x1); x->x2=max(x->x2,y->x2); x->y1=min(x->y1,y->y1); x->y2=max(x->y2,y->y2); } Point *Build(int x,int y,int z) { int k=x + y >> 1; if (x>=y) return x==y?&t[x]:NULL; nth_element(t+x,t+k,t+y+1,z?cmp:cpm); t[k].c[0]=Build(x,k-1,!z); t[k].c[1]=Build(k+1,y,!z); if (t[k].c[0]!=NULL) Update(&t[k],t[k].c[0]); if (t[k].c[1]!=NULL) Update(&t[k],t[k].c[1]); return &t[k]; } void Insert(Point *x,int y,int z) { int k=(z&&x->x<=t[y].x)||(!z&&x->y<=t[y].y); if (x->c[k]==NULL) x->c[k]=&t[y];else Insert(x->c[k],y,!z); Update(x,x->c[k]); } void query(Point *x,int y) { int k=(y&&x->x<=now.x)||(!y&&x->y<=now.y); ans=min(ans,Dis(x,now)); if (x->c[k]!=NULL&&Minimum(x->c[k],now)<ans) query(x->c[k],!y); if (x->c[!k]!=NULL&&Minimum(x->c[!k],now)<ans) query(x->c[!k],!y); } int Query(int y,int x) { ans=INF;now.x=x;now.y=y; query(gf,0);return ans; } } A; int main() { n=Read();m=Read(); for (int i=1;i<=n;i++) A.Get(i); A.gf=A.Build(1,n,0);A.st=n; while (m--) if (Read()-1) printf("%d\n",A.Query(Read(),Read()));else A.Get(++A.st),A.Insert(A.gf,A.st,0); return 0; }