膜了一发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;
 }