BZOJ2648: SJY摆棋子-程序员宅基地

BZOJ2648: SJY摆棋子

题目大意

二维平面内，支持插入点和查询最近点(曼哈顿距离)

K-D Tree的模板题

插入很暴力就不讲了

查询时，$ans$为全局变量，先用该点位置与更新$ans$，算出与左右子树矩阵的曼哈顿距离

如果$ans$$<$子树距离则不下移了

$dl$表与左子树距离，$dr$表与右子树距离，这里有一个很巧妙的剪枝

    if(dl<dr){
        if(dl<ans) 
		    Query(l,tmp);
        if(dr<ans) 
		    Query(r,tmp);
    }
    else{
        if(dr<ans) 
		    Query(r,tmp);
        if(dl<ans) 
		    Query(l,tmp);
    }

表面看上部分似乎与下部分一样，其实这里利用距离确定先后$ans$能尽量接近最终值，起到剪枝效果

My complete code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=1000000;
const LL inf=0x3f3f3f3f;
struct code{
	LL d[2];
}sot[maxn],tmp;
struct node{
	LL son[2],mi[2],mx[2],size;
	code tp;
}tree[maxn];
LL n,m,WD,cnt,nod,root,ans,top;
LL zhan[maxn];
inline LL Read(){
	LL x=0,f=1; char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0'; c=getchar();
	}return x*f;
}
inline void Update(LL now){
	LL l=tree[now].son[0],r=tree[now].son[1];
	tree[now].size=tree[l].size+tree[r].size+1;
	for(LL i=0;i<=1;++i)
	    tree[now].mi[i]=min(tree[now].tp.d[i],min(tree[l].mi[i],tree[r].mi[i])),
	    tree[now].mx[i]=max(tree[now].tp.d[i],max(tree[l].mx[i],tree[r].mx[i]));
}
inline LL Newnode(){
	return top!=0?zhan[top--]:++nod;
}
bool operator < (code g1,code g2){
	return g1.d[WD]<g2.d[WD];
}
LL Build(LL l,LL r,LL wd){
	if(l>r)
	    return 0;
	LL mid=(l+r)>>1,now=Newnode();
	WD=wd,
	nth_element(sot+l,sot+mid,sot+r+1),
	tree[now].tp=sot[mid],
	tree[now].son[0]=Build(l,mid-1,wd^1),
    tree[now].son[1]=Build(mid+1,r,wd^1),
    Update(now);
    return now;
}
void Pai(LL now,LL num){
	LL l=tree[now].son[0],r=tree[now].son[1];
	if(l)
	    Pai(l,num);
	sot[num+tree[l].size+1]=tree[now].tp;
	zhan[++top]=now;
	if(r)
	    Pai(r,num+tree[l].size+1);
}
inline void Check(LL &now,LL wd){
	LL l=tree[now].son[0],r=tree[now].son[1];
	if(tree[now].size*0.75<tree[l].size || tree[now].size*0.75<tree[r].size)
		Pai(now,0),
		now=Build(1,tree[now].size,wd);
}
void Insert(LL &now,code tmp,LL wd){
	if(!now){
		now=Newnode(),
		tree[now].tp=tmp,
		tree[now].son[0]=tree[now].son[1]=0,
		Update(now);
		return;
	}
	tmp.d[wd]<tree[now].tp.d[wd]?Insert(tree[now].son[0],tmp,wd^1):Insert(tree[now].son[1],tmp,wd^1);
	Update(now),
	Check(now,wd);
}
inline LL Dis(code g1,code g2){
	return abs(g1.d[0]-g2.d[0])+abs(g1.d[1]-g2.d[1]);
}
inline LL Mh(code tmp,LL now){
	LL sum=0;
    for(LL i=0;i<=1;++i)
        sum+=max((long long)0,tmp.d[i]-tree[now].mx[i])+max((long long)0,tree[now].mi[i]-tmp.d[i]);
    return sum;
}
void Query(LL now,code tmp){
	LL l=tree[now].son[0],r=tree[now].son[1];
	ans=min(ans,Dis(tmp,tree[now].tp));
	LL dl=inf,dr=inf;
	if(l)
	    dl=min(dl,Mh(tmp,l));
	if(r)
	    dr=min(dr,Mh(tmp,r));
	if(dl<dr){
        if(dl<ans) 
		    Query(l,tmp);
        if(dr<ans) 
		    Query(r,tmp);
    }
    else{
        if(dr<ans) 
		    Query(r,tmp);
        if(dl<ans) 
		    Query(l,tmp);
    }
}
int main(){
	n=Read(),m=Read(),
	tree[0].mi[0]=tree[0].mi[1]=inf,
	tree[0].mx[0]=tree[0].mx[1]=-inf;
	for(LL i=1;i<=n;++i)
		sot[i].d[0]=Read(),
		sot[i].d[1]=Read();
	root=Build(1,n,1);
	while(m--){
		LL op=Read();
		tmp.d[0]=Read(),
		tmp.d[1]=Read();
		if(op==1)
			Insert(root,tmp,1);
		else{
			ans=inf;
			Query(root,tmp);
			printf("%lld\n",ans);
		}
	}
}/*
0 10000
1 1 1
1 1 5
1 2 5
1 5 2
1 6 7
*/