[BZOJ]2648 SJY摆棋子 KD-Tree

2648: SJY摆棋子

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 5049 Solved: 1762
[ 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

鸣谢孙嘉裕

[ Submit][ Status][ Discuss]

HOME Back

　　写了崂山那道题之后做这道题就很轻松了. 就是求最近邻点. 那么每次查询对左右子树的下界进行估价来判断谁更优来剪枝查询. 这道题不用写替罪羊重构也能过. 一发AC嘿嘿嘿.

　　有些人学了之后认为是剪枝后的暴力，实际上可以证明这样最坏是n根号n. 因为假设查询一个矩形的信息的话复杂度直接考虑矩形边界跨过的区域带来的复杂度(因为被完全包含或者被完全不包含的子树肯定不会进入递归)，考虑矩形的一条边所跨过的. 从root进行查询每两次就会与这条边平行剪掉一般的枝条. 那么每两次剪一半，树高又是log，那么推一下式子就会发现是n根号n. 而查最近点对每次查询左右子树就相当于在框一个矩形. 同理可证k维每次查询复杂度是n^(1 - 1 / k).

　　Upd: 突然发现查询曼哈顿距离不是在框矩形??? 那这道题复杂度岂不是玄学??? 不过是矩形查询的复杂度就是如上所说的n根号n啦... 所以这道题正解是什么???

#include<bits/stdc++.h>
#define Boc register char
#define Acce register int
using namespace std;
const int inf = 1 << 30;
const int maxn = 1e6 + 5;
int n, Q, cmpd, qx, qy, ans, opt, root, cur;
inline const int read() {
	Acce x = 0;
	Boc ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
}
struct KDT {
	int ls, rs;
	int mx[2], mn[2], d[2];
	inline friend bool operator < (const KDT &r, const KDT &s) {
		return r.d[cmpd] < s.d[cmpd];
	}
}t[maxn];
inline void update(int x) {
	if (t[x].ls) {
		t[x].mn[0] = min(t[x].mn[0], t[t[x].ls].mn[0]);
		t[x].mx[0] = max(t[x].mx[0], t[t[x].ls].mx[0]);
		t[x].mn[1] = min(t[x].mn[1], t[t[x].ls].mn[1]);
		t[x].mx[1] = max(t[x].mx[1], t[t[x].ls].mx[1]);
	}
	if (t[x].rs) {
		t[x].mn[0] = min(t[x].mn[0], t[t[x].rs].mn[0]);
		t[x].mx[0] = max(t[x].mx[0], t[t[x].rs].mx[0]);
		t[x].mn[1] = min(t[x].mn[1], t[t[x].rs].mn[1]);
		t[x].mx[1] = max(t[x].mx[1], t[t[x].rs].mx[1]);
	}
}
inline int dist(int x) {
	int tmp = 0;
	tmp += max(t[x].mn[0] - qx, 0) + max(qx - t[x].mx[0], 0);
	tmp += max(t[x].mn[1] - qy, 0) + max(qy - t[x].mx[1], 0);
	return tmp;
}
int build(int lf, int rg, int D) {
	int mid = (lf + rg) >> 1;
	cmpd = D;
	nth_element(t + lf + 1, t + mid + 1, t + rg + 1);
	t[mid].mn[0] = t[mid].mx[0] = t[mid].d[0];
	t[mid].mn[1] = t[mid].mx[1] = t[mid].d[1];
	(lf ^ mid) ? t[mid].ls = build(lf, mid - 1, !D) : t[mid].ls = 0;
	(rg ^ mid) ? t[mid].rs = build(mid + 1, rg, !D) : t[mid].rs = 0;
	update(mid);
	return mid;
}
inline void insert() {
	++ cur;
	t[cur].mn[0] = t[cur].mx[0] = t[cur].d[0] = qx;
	t[cur].mn[1] = t[cur].mx[1] = t[cur].d[1] = qy;
	int x = root, D = 0;
	while (true) {
		t[x].mn[0] = min(t[x].mn[0], t[cur].d[0]);
		t[x].mx[0] = max(t[x].mx[0], t[cur].d[0]);
		t[x].mn[1] = min(t[x].mn[1], t[cur].d[1]);
		t[x].mx[1] = max(t[x].mx[1], t[cur].d[1]);
		if (t[cur].d[D] < t[x].d[D]) {
			if (! t[x].ls) {
				t[x].ls = cur;
				break;
			} else x = t[x].ls;
		} else {
			if (! t[x].rs) {
				t[x].rs = cur;
				break;
			} else x = t[x].rs;
		}
		D = !D;
	}
}
void query(int x) {
	int dl, dr;
	ans = min(ans, abs(qx - t[x].d[0]) + abs(qy - t[x].d[1]));
	dl = (t[x].ls) ? dist(t[x].ls) : inf;
	dr = (t[x].rs) ? dist(t[x].rs) : inf;
	if (dl < dr) {
		if (dl < ans) query(t[x].ls);
		if (dr < ans) query(t[x].rs);
	} else {
		if (dr < ans) query(t[x].rs);
		if (dl < ans) query(t[x].ls);
	}
}
int main() {
	n = read(), Q = read();
	for (Acce i = 1; i <= n; ++ i) t[i].d[0] = read(), t[i].d[1] = read();
	root = build(1, n, 0), cur = n;
	for (Acce i = 1; i <= Q; ++ i) {
		opt = read();
		qx = read(), qy = read();
		if (opt & 1) insert();
		else ans = inf, query(root), printf("%d\n", ans);
	}
}

秒客网