bzoj2648 SJY擺棋子

bzoj2648 SJY擺棋子

Description

這天，SJY顯得無聊。在家自己玩。在一個棋盤上，有N個黑色棋子。他每次要麼放到棋盤上一個黑色棋子，要麼放上一個白色棋子，如果是白色棋子，他會找出距離這個白色棋子最近的黑色棋子。此處的距離是 曼哈頓距離 即(|x1-x2|+|y1-y2|) 。現在給出N<=500000個初始棋子。和M<=500000個操作。對於每個白色棋子，輸出距離這個白色棋子最近的黑色棋子的距離。同一個格子可能有多個棋子。  

Input

第一行兩個數 N M 以後M行，每行3個數 t x y 如果t=1 那麼放下一個黑色棋子 如果t=2 那麼放下一個白色棋子

Output

對於每個T=2 輸出一個最小距離  

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output

1
2

HINT

kdtree可以過

K-D Tree第一題。唉，人生若只如初見......

這道題考察的是K-D Tree在最近鄰搜索方面的應用。很顯然，對於黑棋，加入到K-D Tree裡；對於白棋，詢問最近鄰。

下面寫一些自己關於這道題的理解吧：

1.K-D Tree本質上是一種DFS的剪枝優化。

2.每一層對應的區分維度是循環的。由於這道題只有兩維，所以可以利用位運算的抑或操作。

3.在每一層的DFS中，有一個get函數，相當於估計了子區域距離那個點最近是多少，注意是估計。下一次的DFS就從dl和dr中較小的一邊開始。感覺方法還是很巧妙的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 500005
#define inf 1000000000
using namespace std;
int n,m,root,D,ans;
struct data
{
	int d[2],mn[2],mx[2],l,r;
}p[maxn],t[maxn*2],tmp;
bool operator<(data a,data b)
{
	return a.d[D]<b.d[d]; ch="" inline="" int="" while="" x="0,f=1;char">'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int dis(data a,data b)
{
	return abs(a.d[0]-b.d[0])+abs(a.d[1]-b.d[1]);
}
inline void pushup(int k)
{
	int ls=t[k].l,rs=t[k].r;
	F(i,0,1)
	{
		if (ls)
		{
			t[k].mn[i]=min(t[k].mn[i],t[ls].mn[i]);
			t[k].mx[i]=max(t[k].mx[i],t[ls].mx[i]);
		}
		if (rs)
		{
			t[k].mn[i]=min(t[k].mn[i],t[rs].mn[i]);
			t[k].mx[i]=max(t[k].mx[i],t[rs].mx[i]);
		}
	}
}
inline int build(int l,int r,int now)
{
	D=now;
	int mid=(l+r)>>1;
	nth_element(p+l,p+mid,p+r+1);
	t[mid]=p[mid];
	F(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid].d[i];
	if (l<mid) .l="build(l,mid-1,now^1);" .r="build(mid+1,r,now^1);" data="" if="" inline="" int="" return="" tmp="0;" void="">=t[k].d[now])
	{
		if (t[k].r) insert(t[k].r,now^1);
		else
		{
			t[k].r=++n;t[n]=tmp;
			F(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].d[i];
		}
	}
	else
	{
		if (t[k].l) insert(t[k].l,now^1);
		else
		{
			t[k].l=++n;t[n]=tmp;
			F(i,0,1) t[n].mn[i]=t[n].mx[i]=t[n].d[i];
		}
	}
	pushup(k);
}
inline void query(int k,int now)
{
	int d,dl=inf,dr=inf;
	d=dis(t[k],tmp);
	ans=min(ans,d);
	if (t[k].l) dl=get(t[k].l,tmp);
	if (t[k].r) dr=get(t[k].r,tmp);
	if (dl<dr) .l="p[i].r=0;p[i].d[0]=read();p[i].d[1]=read();}" ans="inf;" else="" if="" int="" n="read();m=read();" opt="=1)" pre="" return="" root="build(1,n,0);" tmp.l="tmp.r=0;" while=""><p>
</p>
   
</dr)></mid)></b.d[d];></algorithm></cstdlib></cmath></cstring></cstdio></iostream>