Lvat_s Blog

这个题和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)的卡常版本，比我快的不知道到哪里去了（还是不放比较好……）（就是查询时做了一些神奇的优化）