BZOJ 2648(SJY擺棋子

 

2648: SJY擺棋子

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 1180 Solved: 391
[Submit][Status][Discuss]

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可以過

 

Source

鳴謝 孫嘉裕

 

提示中已有kd-tree了，那麼百度一下

考慮平面上一堆點，先找出橫坐標中位數的點，取出，對著切一刀，剩下點分為2半

然後對其中一邊豎著切，再橫著切。。。。

 

 

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (1000000000)
#define F (100000007)
#define MAXN (500000+10)
#define MAXM (500000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n,m;

int cmp_d=0;
class node
{
public:
	int x[2];
	int l,r,minv[2],maxv[2];

	node(){}
	node(int a,int b){MEM(x) l=r=0; x[0]=a,x[1]=b; Rep(i,2) minv[i]=maxv[i]=x[i];}



	int& operator[](int i){return x[i];	} 
};

int dis(node a,node b){
	int ans=0;
	Rep(i,2) ans+=abs(a.x[i]-b.x[i]);
	return ans;	
}

int dis2(node p,node a) // 點p和方形區域a的歐幾裡德距離 
{
	int ans=0;
	Rep(i,2)
	{
		if (p.x[i]a.maxv[i]) ans+=p.x[i]-a.maxv[i];
	}
	return ans;
}


int cmp(node a,node b){return a[cmp_d]>1;
	
		cmp_d=nowd;
		nth_element(a+L+1,a+m+1,a+R+1,cmp);
		
		if (L^m) a[m].l=build(L,m-1,nowd^1);
		if (R^m) a[m].r=build(m+1,R,nowd^1);
		
		update(a[m]);
		
		return m;
		
	} 
	
	int root;
	void _build(int L,int R,int nowd)
	{
		root=build(L,R,nowd);
	}
	
	void insert(int o,int k,int nowd)
	{
		int p=a[o].x[nowd];
		int p2=a[k].x[nowd];
		
		if (p2<=p) 
		{
			if (a[o].l) 
				insert(a[o].l,k,nowd^1);
			else a[o].l=k;
		}
		else
		{
			if (a[o].r)
				insert(a[o].r,k,nowd^1);		
			else a[o].r=k;
				
		}
		
			
		update(a[o]);	
			
	}
	void _insert(int k,int nowd)
	{
		int p=root;
		insert(root,k,nowd);		
	}
	
	
	node _p;
	int _ans;
	
	void ask_min_dis(int o)
	{
		if (o==0) return;
		_ans=min(_ans,dis(a[o],_p));
		
		int ans1=a[o].l ? dis2(_p,a[a[o].l]) : INF;	// 點p到區域內任意一點的距離的最小值
		int ans2=a[o].r ? dis2(_p,a[a[o].r]) : INF;
		
		
		
		if (ans1>n>>m;
	For(i,n)
	{
		int x,y;
		scanf(%d%d,&x,&y);
		S.a[i]=node(x,y);
	} 
	S.a[++n]=node(INF,INF);
	S._build(1,n,0);
	For(i,m)
	{
		int p,x,y;
		scanf(%d%d%d,&p,&x,&y);
		if (p==1)
		{
			S.a[++n]=node(x,y);
			S._insert(n,0);
		} else {
			printf(%d
,S._ask(node(x,y)));
						
		}
	}
	
	
	
	return 0;
}