2648: SJY摆棋子
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 4766 Solved: 1646
[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可以过
题目链接：BZOj 2648
题目本身输入描述有问题，第一行是已经存在$N$个黑棋，然后接下来的$M$行才是操作，因此把$N$个黑棋拿去建树，然后后面的黑棋拿去插到树上，$KD-tree$应用题之一
代码：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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 500010;
int idx;
struct KD
{
int ls, rs, d[2], mn[2], mx[2];
} T[N << 1];
struct info
{
int d[2];
bool operator<(const info &rhs)const
{
return d[idx] < rhs.d[idx];
}
} arr[N];
int sz, rt;
int ans;
void init()
{
sz = rt = 0;
}
inline void pushup(const int &k)
{
if (T[k].ls)
{
for (int i = 0; i < 2; ++i)
{
T[k].mn[i] = min(T[k].mn[i], T[T[k].ls].mn[i]);
T[k].mx[i] = max(T[k].mx[i], T[T[k].ls].mx[i]);
}
}
if (T[k].rs)
{
for (int i = 0; i < 2; ++i)
{
T[k].mn[i] = min(T[k].mn[i], T[T[k].rs].mn[i]);
T[k].mx[i] = max(T[k].mx[i], T[T[k].rs].mx[i]);
}
}
}
void build(int &k, int l, int r, int dim)
{
k = ++sz;
idx = dim;
int mid = MID(l, r);
nth_element(arr + l, arr + mid, arr + r + 1);
for (int i = 0; i < 2; ++i)
T[k].d[i] = T[k].mn[i] = T[k].mx[i] = arr[mid].d[i];
T[k].ls = T[k].rs = 0;
if (l < mid)
build(T[k].ls, l, mid - 1, dim ^ 1);
if (mid < r)
build(T[k].rs, mid + 1, r, dim ^ 1);
pushup(k);
}
void ins(int &k, int *d, int dim)
{
if (!k)
{
k = ++sz;
for (int i = 0; i < 2; ++i)
T[k].d[i] = T[k].mn[i] = T[k].mx[i] = d[i];
T[k].ls = T[k].rs = 0;
}
else
{
if (d[dim] <= T[k].d[dim])
ins(T[k].ls, d, dim ^ 1);
else
ins(T[k].rs, d, dim ^ 1);
pushup(k);
}
}
inline int partionMin(int k, int *d)
{
int dx = 0;
if (d[0] > T[k].mx[0])
dx += d[0] - T[k].mx[0];
if (d[0] < T[k].mn[0])
dx += T[k].mn[0] - d[0];
if (d[1] > T[k].mx[1])
dx += d[1] - T[k].mx[1];
if (d[1] < T[k].mn[1])
dx += T[k].mn[1] - d[1];
return dx;
}
void Find(int k, int *d)
{
int dm = abs(T[k].d[0] - d[0]) + abs(T[k].d[1] - d[1]);
ans = min(ans, dm);
int dl = T[k].ls ? partionMin(T[k].ls, d) : 2e9, dr = T[k].rs ? partionMin(T[k].rs, d) : 2e9;
if (dl < dr)
{
if (dl < ans)
Find(T[k].ls, d);
if (dr < ans)
Find(T[k].rs, d);
}
else
{
if (dr < ans)
Find(T[k].rs, d);
if (dl < ans)
Find(T[k].ls, d);
}
}
int main(void)
{
int n, m, d[2], t, i;
while (~scanf("%d%d", &n, &m))
{
init();
for (i = 1; i <= n; ++i)
scanf("%d%d", &arr[i].d[0], &arr[i].d[1]);
build(rt, 1, n, 0);
while (m--)
{
scanf("%d%d%d", &t, &d[0], &d[1]);
if (t == 1)
ins(rt, d, 0);
else
{
ans = 2e9;
Find(rt, d);
printf("%d\n", ans);
}
}
}
return 0;
}