这个题和BZOJ2648基本是一样的
理论上直接交就能过
但是在学校的OJ上被卡到95分了很悲伤
算了就放这个BZOJ可以过但是被卡常的版本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const register int N=500005,INF=2100000000;
static int n,m,Sort_Tag,root,ans=INF;
struct KDTree{
int l,r,d[2],mn[2],mx[2];
KDTree(){}
KDTree(register int x,register int y){mn[0]=mx[0]=d[0]=x;mn[1]=mx[1]=d[1]=y;l=r=0;}
inline friend bool operator<(register KDTree A,register KDTree B){return A.d[Sort_Tag]<B.d[Sort_Tag];}
}tree[N<<2],Temp;
inline int Max(register int x,register int y){return x<y?y:x;}
inline int Min(register int x,register int y){return x<y?x:y;}
inline int Abs(register int x){return x>0?x:-x;}
inline int Dist(register KDTree A,register KDTree B){return Abs(A.d[0]-B.d[0])+Abs(A.d[1]-B.d[1]);}
inline void Pushup(register int rt){
if(tree[rt].l){
tree[rt].mn[0]=Min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
tree[rt].mn[1]=Min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
tree[rt].mx[0]=Max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
tree[rt].mx[1]=Max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
}
if(tree[rt].r){
tree[rt].mn[0]=Min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
tree[rt].mn[1]=Min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
tree[rt].mx[0]=Max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
tree[rt].mx[1]=Max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
}
}
inline int Build(register int l,register int r,register int D){
Sort_Tag=D;
register int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
inline void _Insert(register int rt,register int D){
if(Temp.d[D]>=tree[rt].d[D]){
if(tree[rt].r)_Insert(tree[rt].r,!D);
else {tree[rt].r=++n;tree[n]=Temp;}
}
else {
if(tree[rt].l)_Insert(tree[rt].l,!D);
else {tree[rt].l=++n;tree[n]=Temp;}
}
Pushup(rt);
}
inline void Insert(register int x,register int y){
Temp=KDTree(x,y);
_Insert(root,0);
}
inline int MxDist(register int rt,register int x,register int y){
return Max(tree[rt].mn[0]-x,0)+Max(tree[rt].mn[1]-y,0)+Max(x-tree[rt].mx[0],0)+Max(y-tree[rt].mx[1],0);
}
inline void _Query(register int rt){
register int Dl=INF,Dr=INF,Dm=Dist(tree[rt],Temp);
ans=Min(ans,Dm);
if(tree[rt].l)Dl=MxDist(tree[rt].l,Temp.d[0],Temp.d[1]);
if(tree[rt].r)Dr=MxDist(tree[rt].r,Temp.d[0],Temp.d[1]);
if(Dl<Dr){
if(Dl<ans)_Query(tree[rt].l);
if(Dr<ans)_Query(tree[rt].r);
}
else {
if(Dr<ans)_Query(tree[rt].r);
if(Dl<ans)_Query(tree[rt].l);
}
}
inline int Query(register int x,register int y){
Temp=KDTree(x,y);ans=INF;
_Query(root);
return ans;
}
inline void Read(register int &x){
register char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
int main(){
freopen("2716.in","r",stdin);
freopen("2716.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(tree[i].d[0]),Read(tree[i].d[1]);
root=Build(1,n,0);
for(register int i=1;i<=m;i++){
register int opt,x,y;
Read(opt);Read(x);Read(y);
if(opt==1)Insert(x,y);
if(opt==2)printf("%d\n",Query(x,y));
}
return 0;
}
lzz(C_SUNSHINE)的卡常版本，比我快的不知道到哪里去了（还是不放比较好……）（就是查询时做了一些神奇的优化）
