【34.25%】【BZOJ 2648】SJY摆棋子

Time Limit: 20 Sec Memory Limit: 128 MB

Submit: 2718 Solved: 931

[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

鸣谢孙嘉裕

【题解】

用kdtree来做。

插入的操作的话。可以用数组来模拟指针(不喜欢用,太麻烦)。将kdtree弄成一个类似二叉搜索树的东西。(别管退化的问题了)；

然后用两个二维数组ma_x[2],mi_n[2]来维护某个子树里面点的x,y坐标形成的最大矩形的左上角和右下角(不一定存在这样的矩形).

然后我们写估价函数的思路就是，如果要询问的点在这个矩形里面。则估价函数返回一个最小的值0.否则返回这个点到这个矩形的边缘所需要的最小曼哈顿距离。

估价函数这样写。

int gujia_min(int rt)

{

int temp = 0;

for (int i = 0; i <= 1; i++)

{

temp += max(0, op.d[i]-t[rt].ma_x[i]);

temp += max(0, t[rt].mi_n[i] - op.d[i]);

}

return temp;

}

思路是既然这个点在这个子树的矩形内。那最近点就有很大的可能在那个子树里面(不是绝对！)；

想象一下一个点被一个矩形包围。那它的最近点“看起来”不就应该是在这个矩形内或者矩形边上吗。

当然我们已经说了。这个是不一定的。你可以很容易举出反例的。

具体实现看代码吧。

【代码】

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAX_SIZE = 1500000;

const int MAXN = 509000;

const int INF = 2100000000;

struct point

{

	int d[2];

	int ma_x[2], mi_n[2], l, r;

};

point t[MAX_SIZE],p[MAXN],op;

int n, m,totn = 0,root,now,ans; //totn用于创建新的节点。

bool cmp(point a, point b)

{

	if (a.d[now] < b.d[now])

		return true;

	return false;

}

void push_up(int rt)

{

	int l = t[rt].l, r = t[rt].r;

	for (int i = 0; i <= 1; i++)

	{

		if (l)

		{

			t[rt].ma_x[i] = max(t[l].ma_x[i], t[rt].ma_x[i]);

			t[rt].mi_n[i] = min(t[l].mi_n[i], t[rt].mi_n[i]);

		}

		if (r)

		{

			t[rt].ma_x[i] = max(t[r].ma_x[i], t[rt].ma_x[i]);

			t[rt].mi_n[i] = min(t[r].mi_n[i], t[rt].mi_n[i]);

		}

	}

}

int build(int begin, int end, int fx)

{

	now = fx;

	int m = (begin + end) >> 1;

	nth_element(p + begin, p + m, p + end + 1, cmp);

	int temp = ++totn; //新建的节点要保存下来。

	for (int i = 0; i <= 1; i++)

	{

		t[temp].d[i] = p[m].d[i];

		t[temp].ma_x[i] = t[temp].mi_n[i] = p[m].d[i];

	}

	if (begin < m)

		t[temp].l = build(begin, m - 1, 1 - fx);

	if (m < end)

		t[temp].r = build(m + 1, end, 1 - fx);

	push_up(temp);

	return temp;

}

void input_data()

{

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++)

		scanf("%d%d", &p[i].d[0], &p[i].d[1]);

	root = build(1, n, 0);

}

void insert(int &rt,int fx)

{

	if (rt == 0)

	{

		rt = ++totn;

		for (int i = 0; i <= 1; i++)

		{

			t[rt].d[i] = op.d[i];

			t[rt].ma_x[i] = t[rt].mi_n[i] = op.d[i];

		}

		return;//这里的return不能省略。不然叶子节点也会执行push_up操作。

	}

	else

		if (op.d[fx] < t[rt].d[fx])

			insert(t[rt].l, 1 - fx);

		else

			insert(t[rt].r, 1 - fx);

	push_up(rt);//因为插入了元素，修改了点。所以要更新ma_x,mi_n值。

}

int get_dis(point a, point b)

{

	return abs(a.d[0] - b.d[0]) + abs(a.d[1] - b.d[1]);

}

int gujia_min(int rt)

{

	int temp = 0;

	for (int i = 0; i <= 1; i++)

	{

		temp += max(0, op.d[i]-t[rt].ma_x[i]);

		temp += max(0, t[rt].mi_n[i] - op.d[i]);

	}

	return temp;

}

void query_min(int rt)

{

	int dis = get_dis(t[rt], op);

	ans = min(ans, dis);

	int gl = INF, gr = INF;

	int l = t[rt].l, r = t[rt].r;

	if (l)

		gl = gujia_min(l);

	if (r)

		gr = gujia_min(r);

	if (gl < gr)

	{

		if (ans > gl)

			query_min(l);

		if (ans > gr)

			query_min(r);

	}

	else

	{

		if (ans > gr)

			query_min(r);

		if (ans > gl)

			query_min(l);

	}

}

void output_ans()

{

	for (int i = 1; i <= m; i++)

	{

		int cs;

		scanf("%d%d%d", &cs, &op.d[0], &op.d[1]);

		if (cs == 1)

			insert(root,0);

		else

			if (cs == 2)

			{

				ans = INF;

				query_min(root);

				printf("%d\n", ans);

			}

	}

}

int main()

{

	//freopen("F:\\rush.txt", "r", stdin);

	input_data();

	output_ans();

	return 0;

}

巴特西