「BZOJ 2648」SJY摆棋子

发表于

这天，SJY 显得无聊。在家自己玩。在一个棋盘上，有 NN 个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即 (∣x1−x2∣+∣y1−y2∣)(|x_1-x_2|+|y_1-y_2|) 。现在给出 NN 个初始棋子和 MM 个操作,对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Constraints

n,m≤500000n,m \leq 500000

Solution

退役之前学一下 kd-tree ，模板借鉴了 ljh2000 大爷の模板 。

具体原理见 Sengxian 大爷の博客 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e6+5;
const int inf=(1<<30);
int n,m,root,nowd,op,x,y,a,b,ans;
struct node{int l,r,mx[2],mn[2],d[2];}t[N];
int read()
{
	int 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*10+c-'0';c=getchar();}
	return x*f;
}
int ab(int x){return x>=0?x:-x;}
void Max(int& a,int b){if(b>a)a=b;}
void Min(int& a,int b){if(b<a)a=b;}
bool cmp(node a,node b)
{
	if(a.d[nowd]==b.d[nowd])return a.d[nowd^1]<b.d[nowd^1];
	return a.d[nowd]<b.d[nowd];
}
void update(int x,int y)
{
	Max(t[x].mx[0],t[y].mx[0]);Max(t[x].mx[1],t[y].mx[1]);
	Min(t[x].mn[0],t[y].mn[0]);Min(t[x].mn[1],t[y].mn[1]);
}
void modify(int x)
{
	if(t[x].l)update(x,t[x].l);
	if(t[x].r)update(x,t[x].r);
}
int build(int l,int r,int D)
{
	int mid=(l+r)>>1;nowd=D;
	nth_element(t+l+1,t+mid+1,t+r+1,cmp);
	if(l!=mid)t[mid].l=build(l,mid-1,D^1);
	if(r!=mid)t[mid].r=build(mid+1,r,D^1);
	t[mid].mx[0]=t[mid].mn[0]=t[mid].d[0];
	t[mid].mx[1]=t[mid].mn[1]=t[mid].d[1];
	modify(mid);return mid;
}
void insert(int x)
{
	int p=root,D=0;
	while(true)
	{
		update(p,x);
		if(t[x].d[D]>=t[p].d[D])
		{
			if(!t[p].r){t[p].r=x;return;}
			else p=t[p].r;
		}
		else
		{
			if(!t[p].l){t[p].l=x;return;}
			else p=t[p].l;
		}
		D=!D;
	}
}
int dis(int x)
{
	int dist=0;
	if(a<t[x].mn[0])dist+=t[x].mn[0]-a;
	if(a>t[x].mx[0])dist+=a-t[x].mx[0];
	if(b<t[x].mn[1])dist+=t[x].mn[1]-b;
	if(b>t[x].mx[1])dist+=b-t[x].mx[1];
	return dist;
}
void query(int x)
{
	int dl,dr;Min(ans,ab(t[x].d[0]-a)+ab(t[x].d[1]-b));
	if(t[x].l)dl=dis(t[x].l);else dl=inf;
	if(t[x].r)dr=dis(t[x].r);else dr=inf;
	if(dl<dr)
	{
		if(dl<ans)query(t[x].l);
		if(dr<ans)query(t[x].r);
	}
	else
	{
		if(dr<ans)query(t[x].r);
		if(dl<ans)query(t[x].l);
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		t[i].d[0]=read(),t[i].d[1]=read();
	root=build(1,n,0);
	while(m--)
	{
		op=read();x=read();y=read();
		if(op==1)
		{
			n++;t[n].mx[0]=t[n].mn[0]=t[n].d[0]=x;
			t[n].mx[1]=t[n].mn[1]=t[n].d[1]=y;insert(n);
		}
		else
		{
			ans=inf;a=x;b=y;
			query(root);printf("%d\n",ans);
		}
	}
	return 0;
}