首页 > ACM题库 > HDU-杭电 > hdu 2475 Box-计算几何-[解题报告]C++
2014
01-26

hdu 2475 Box-计算几何-[解题报告]C++

Box

问题描述 :

There are N boxes on the ground, which are labeled by numbers from 1 to N. The boxes are magical, the size of each one can be enlarged or reduced arbitrarily.
Jack can perform the “MOVE x y” operation to the boxes: take out box x; if y = 0, put it on the ground; Otherwise, put it inside box y. All the boxes inside box x remain the same. It is possible that an operation is illegal, that is, if box y is contained (directly or indirectly) by box x, or if y is equal to x.
In the following picture, box 2 and 4 are directly inside box 6, box 3 is directly inside box 4, box 5 is directly inside box 1, box 1 and 6 are on the ground.

The picture below shows the state after Jack performs “MOVE 4 1”:

Then he performs “MOVE 3 0”, the state becomes:

During a sequence of MOVE operations, Jack wants to know the root box of a specified box. The root box of box x is defined as the most outside box which contains box x. In the last picture, the root box of box 5 is box 1, and box 3’s root box is itself.

输入:

Input contains several test cases.
For each test case, the first line has an integer N (1 <= N <= 50000), representing the number of boxes.
Next line has N integers: a1, a2, a3, … , aN (0 <= ai <= N), describing the initial state of the boxes. If ai is 0, box i is on the ground, it is not contained by any box; Otherwise, box i is directly inside box ai. It is guaranteed that the input state is always correct (No loop exists).
Next line has an integer M (1 <= M <= 100000), representing the number of MOVE operations and queries.
On the next M lines, each line contains a MOVE operation or a query:
1.  MOVE x y, 1 <= x <= N, 0 <= y <= N, which is described above. If an operation is illegal, just ignore it.
2.  QUERY x, 1 <= x <= N, output the root box of box x.

输出:

Input contains several test cases.
For each test case, the first line has an integer N (1 <= N <= 50000), representing the number of boxes.
Next line has N integers: a1, a2, a3, … , aN (0 <= ai <= N), describing the initial state of the boxes. If ai is 0, box i is on the ground, it is not contained by any box; Otherwise, box i is directly inside box ai. It is guaranteed that the input state is always correct (No loop exists).
Next line has an integer M (1 <= M <= 100000), representing the number of MOVE operations and queries.
On the next M lines, each line contains a MOVE operation or a query:
1.  MOVE x y, 1 <= x <= N, 0 <= y <= N, which is described above. If an operation is illegal, just ignore it.
2.  QUERY x, 1 <= x <= N, output the root box of box x.

样例输入:

2
0 1
5
QUERY 1
QUERY 2
MOVE 2 0
MOVE 1 2
QUERY 1
6
0 6 4 6 1 0
4
MOVE 4 1
QUERY 3
MOVE 1 4
QUERY 1

样例输出:

1
1
2

1
1

        不错的一道题, 自己怎么也写不出来, 于是去问了风神。 把每个箱子看成一个括号, 箱子a在箱子b里面, 就是括号b在括号a里面。

这样第一组样例就变成了(【1】(【2】)【4】)【3】       (【x】表示第x个节点), 这样就有序了, 然后装进splay形成一个森林。

0 1 就变成了

(  (  )  )

1 2 4 3

0 6 4 6 1 0就变成了

(  (    )  )     (  (  )   (  (  )   )   )

1 5 11 7    6 2 8 4 3 9 10 12

违法操作有两种, 违法的操作有两个, 第一种是 a == b, 第二种是 b 是 a的孩子, 对于这个情况, 把节点 a 旋转至根节点, a + n 旋转到 a 下面, 然后从 b 开始不断往上找b的父亲, 如果发现有a + n, 则说明 b 是  a  的孩子。

移动操作可以先把 [a, a + n] 移出来单独成一棵树。 然后把 b 移动到根, 再把 b 的下一个移动到 b 的下面, 最后把 [a, a + n] 移动到 b 的右孩子的下面就OK了

询问操作就比较简单, 直接把 a 移动到 根 从 a 开始找最左边的节点就是了。

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int N = 50007;

int size, head[N], n;
int pr[N], next[N], in[N];
struct Edge
{
	int v, next;

	void ini(int a, int b)
	{
		v = b;
		next = head[a];
		head[a] = size++;
	}
};
Edge edge[N];
int ch[N << 1][2], fa[N << 1];

void build(int x) //建树(size 表示最后加进来的节点)
{
	fa[x] = size;
	ch[size][1] = x;
	size = x;
	for(int i = head[x]; i != -1; i = edge[i].next)
	{
		int v = edge[i].v;
		build(v);
	}
	fa[x + n] = size;
	ch[size][1] = x + n;
	size = x + n;
}

void init()
{
	memset(ch, 0, sizeof(ch));
	for(int i = next[0]; i != -1; i = next[i])
	{
		size = 0;
		build(i);
	}
}

inline void rotate(int x, bool f)
{
	int y = fa[x];
	int z = fa[y];
	ch[y][!f] = ch[x][f];
	fa[ch[x][f]] = y;
	fa[x] = z;
	if(z)
		ch[z][ch[z][1] == y] = x;
	ch[x][f] = y;
	fa[y] = x;
}

void splay(int x, int g)
{
	int y = fa[x];
	while(y != g)
	{
		int z = fa[y];
		bool f = (ch[y][0] == x);
		if(z != g && f == (ch[z][0] == y))
			rotate(y, f);
		rotate(x, f);
		y = fa[x];
	}
}

void move(int a, int b)
{
	if(a == b)
		return ;
	splay(a, 0);
	splay(a + n, a);
	for(int i = b; i; i = fa[i]) //判断b是否为a的孩子
		if(ch[a + n][0] == i)
			return ;
	int x, y;
	x = ch[a][0];
	y = ch[a + n][1];
	ch[a][0] = ch[a + n][1] = fa[x] = fa[y] = 0; //把[a, a + n]取出来
	if(x && y)
	{
		while(ch[y][0])
			y = ch[y][0];
		ch[y][0] = x;
		fa[x] = y;
	}
	if(b == 0) //[a, a + n]已经独立为一棵树了
		return ;
	splay(b, 0);
	int i;
	for(i = ch[b][1]; ch[i][0]; i = ch[i][0]) ; //找b后面的一个节点
	splay(i, b);
	ch[i][0] = a;
	fa[a] = i;
}

int que(int a)
{
	splay(a, 0); //把a移动到根,方便找这棵树的最小值
	for(; ch[a][0]; a = ch[a][0]) ;
	return a;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	bool f = false;
	while(~scanf("%d", &n))
	{
		if(f)
			puts("");
		else
			f = true;
		int tmp = 0;
		pr[0] = next[0] = -1;
		size = 0;
		memset(head, -1, sizeof(head));
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", in + i);
			if(in[i])
				edge[size].ini(in[i], i);
			else
			{
				next[tmp] = i;
				next[i] = -1;
				pr[i] = tmp;
				tmp = i;
			}
		}
		init();
		int m;
		scanf("%d", &m);
		while(m--)
		{
			char s[10];
			int a;
			scanf("%s%d", s, &a);
			if(s[0] == 'M')
			{
				int b;
				scanf("%d", &b);
				move(a, b);
			}
			else
				printf("%d\n", que(a));
		}
	}
	return 0;
}

解题转自:http://blog.csdn.net/afafsdg/article/details/8053656