【线段树 + 离散化 + 详细注释】北大 poj 2528 Mayor's posters

第二次

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://poj.org/problem?id=2528
    Name  : 2528 Mayor's posters

    Date  : Saturday, October 1, 2011
    Time Stage : one and half an hours

    Result: 
9378439	panyanyany
2528
Accepted	1248K	79MS	C++
3804B	2011-10-01 00:36:01
9378423	panyanyany
2528
Wrong Answer			C++
3707B	2011-10-01 00:30:47
								

Test Data :

Review :
第二次做，还是有很多地方没有注意到的。比如 2 * n，以及递归到达叶子时没有判断 和 退出
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std ;

typedef __int64 LL ;

int max (int lhs, int rhs)
{
	return (lhs > rhs ? lhs : rhs) ;
}

int min (int lhs, int rhs)
{
	return lhs < rhs ? lhs : rhs ;
}

#define MAXSIZE 10010

#define L(n) 		((n) << 1)
#define R(n) 		(((n) << 1) + 1)
#define MID(a, b) 	(((a) + (b)) >> 1)

// 此结构体用来映射新的端点值
typedef struct {
	bool	isLeft ;	// 判断此端点是否左端点
	int 	id ;		// 标记此站点是第几个端点
	int		val ;		// 此端点的原来的值
} MAP ;

// 此结构体用来做线段树的节点
typedef struct {
	int		id ;			// 海报序号，若为0则表示在[left,right]内海报的张数不确定
	int		left, right ;	// left , right 分别代表此区间的 左，右 端点
} NODE ;

int		tcase, n, cnt ;
bool	flag[MAXSIZE] ;
int		left[MAXSIZE], right[MAXSIZE] ;
MAP		map[MAXSIZE * 2] ;
NODE	tree[MAXSIZE * 14] ;

int cmp(MAP lhs, MAP rhs)
{
	return lhs.val < rhs.val ;
}

void build (int node, int left, int right)
{
	tree[node].id 		= 0 ;
	tree[node].left		= left ;
	tree[node].right	= right ;
	
	if (left == right)
		return ;
	int mid = MID (left, right) ;
	build (L(node), left, mid) ;
	build (R(node), mid + 1, right) ;
}

void update (int node, int left, int right, int NewId)
{
	// 若张贴的海报刚好覆盖当前区间，则当前区间的 id 为该海报的 id
	if (tree[node].left == left && tree[node].right == right ||
		tree[node].left == tree[node].right)
	{
		tree[node].id = NewId ;
		return ;
	}
	
	// 若海报不足以完全覆盖当前区间
	
	// 若此区间之前已经被某海报完全覆盖
	if (tree[node].id != 0)
	{
		tree[L(node)].id = tree[node].id ;		// 假设左子树不被海报覆盖，则其 id 为根区间的 id
		tree[R(node)].id = tree[node].id ;		// 假设右子树不被海报覆盖，则其 id 为根区间的 id
		tree[node].id	 = 0 ;					// 因为在此区间内有两张海报，则此区间的 id 为不确定
	}
	
	int mid = MID (tree[node].left, tree[node].right) ;
	
	// 若海报仅能覆盖左半区间
	if (right <= mid)
		update (L(node), left, right, NewId) ;
	// 若海报仅能覆盖右半区间
	else if (mid < left)
		update (R(node), left, right, NewId) ;
	// 若海报横跨本区间中部
	else
	{
		update (L(node), left, mid, NewId) ;
		update (R(node), mid + 1, right, NewId) ;
	}
}

void count (int node)
{
	// 若此区间恰有一张海报
	if (tree[node].id)
	{
		// 若此海报未被记录
		if (flag[tree[node].id] == false)
		{
			flag[tree[node].id] = true ;
			++cnt ;
		}
		return ;
	}
	
	// 已经到达叶子，此节点仍为不确定状态，则退出
	if (tree[node].left == tree[node].right)
		return ;
	
	// 若此区间的海报数量不确定
	// 则递归查找子区间
	count (L(node)) ;
	count (R(node)) ;
}

int main ()
{
	int	i, j ;
	int t, tmp ;
	while (scanf ("%d", &tcase) != EOF)
	{
		while (tcase--)
		{
			scanf ("%d", &n) ;
			for (i = 1 ; i <= n ; ++i)
			{
				scanf ("%d%d", &left[i], &right[i]) ;
				map[i * 2 - 1].id 		= i ;
				map[i * 2 - 1].isLeft 	= true ;
				map[i * 2 - 1].val		= left[i] ;
				
				map[i * 2].id			= i ;
				map[i * 2].isLeft		= false ;
				map[i * 2].val			= right[i] ;
			}
			// 把端点值按从小到大排序, 注意 2 * n
			sort (map + 1, map + 1 + 2 * n, cmp) ;
			
			// 离散化
			tmp = map[1].val ;	// tmp 用来判断是否与前一个原始端点值相同
			t = 1 ;				// t 作为新的端点值（离散化）
			
			// 注意 2 * n
			for (i = 1 ; i <= 2 * n ; ++i)
			{
				if (tmp != map[i].val)
				{
					tmp = map[i].val ;
					++t ;
				}
				if (map[i].isLeft == true)
				{
					left[map[i].id] = t ;
				}
				else
				{
					right[map[i].id] = t ;
				}
			}
			// 注意 2 * t
			build (1, 1, 2 * t) ;	// 构造线段树
			// 更新线段树
			for (i = 1 ; i <= n ; ++i)
				update (1, left[i], right[i], i) ;
				
			memset (flag, false, sizeof (flag)) ;
			cnt = 0 ;
			count (1) ;
			printf ("%d\n", cnt) ;
		}
	}
	return 0 ;
}

第一次

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://poj.org/problem?id=2528
    Name  : 2528 Mayor's posters

    Date  : Monday, September 26, 2011
    Time Stage : Three hours

    Result: 
9363927	panyanyany
2528
Accepted	1252K	94MS	C++
3304B	2011-09-26 21:12:59
9363885	panyanyany
2528
Accepted	1272K	94MS	C++
3738B	2011-09-26 21:05:46
9363864	panyanyany
2528
Wrong Answer			C++
3616B	2011-09-26 21:01:08
9363854	panyanyany
2528
Wrong Answer			C++
3612B	2011-09-26 20:59:25
9363846	panyanyany
2528
Compile Error
		C++
3544B	2011-09-26 20:58:31
9363671	panyanyany
2528
Time Limit Exceeded			C++
3370B	2011-09-26 20:16:14
9363662	panyanyany
2528
Runtime Error			C++
3369B	2011-09-26 20:15:02
9363631	panyanyany
2528
Runtime Error			C++
3337B	2011-09-26 20:09:37
9363613	panyanyany
2528
Runtime Error			C++
3341B	2011-09-26 20:06:49
9363610	panyanyany
2528
Runtime Error			C++
3332B	2011-09-26 20:06:02
9363604	panyanyany
2528
Runtime Error			C++
3332B	2011-09-26 20:05:09

Test Data :

Review : 
首先感谢几位大牛的解题报告：
AC_Von，http://www.cnblogs.com/vongang/archive/2011/08/10/2133869.html
kuangbin，http://www.cnblogs.com/kuangbin/archive/2011/08/15/2139931.html

思路：

这题的思想，主要是离散化，当然还有一些小技巧。
离散化，大概就是：
	由于不可能开1000,0000的数组，又注意到其实际有效数据才
10000 对，在最坏的情况下，将有 2000 个不同的数据。
比如：
n = 5 ;
1，200，3，5000，8999，100000， 999，9999999999
若直接以上面的数字作下标，则起码要开 9999999999 大小的数组，
显然是不可能的。
若将上面的数列排序，则：
1，3，200，999，5000，8999，100000，9999999999
根据排序的顺序，映射新的下标：
1，3，200，999，5000，8999，100000，9999999999
1，2，3，  4，  5，   6，   7，     8
则我们其实只开 8 大小的数组就可以了！

血泪史：

一开始数组开小了，无限RE，
后来用一个循环去遍历整棵树，TLE，
于是将 count() 函数的查找改为递归模式，同时修改 update() 函数，正式确定
Tree[node].sum 的作用，当为 0 时，表示当前区间的海报数量不确定，
当为正整数值时，表示当前区间只有某海报
后来VC6或者VA的复制发了神经，后面截断一大片，又CE，
重新复制后，WA，
最后一次改错，是标记重复

//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std ;

typedef __int64 LL ;

int max (int lhs, int rhs)
{
	return (lhs > rhs ? lhs : rhs) ;
}

int min (int lhs, int rhs)
{
	return lhs < rhs ? lhs : rhs ;
}

#define MAXSIZE 10010

#define L(n)	((n) << 1)
#define R(n)	(((n) << 1) + 1)

typedef struct {
	int		id ;
	int		endVal ;
	bool	isLeft ;
} TAG ;

typedef struct {
	int id ;
	int left, right ;
} NODE ;

bool	flag[MAXSIZE * 2] ;
int		tcase, n, cnt ;
int		num[MAXSIZE][2] ;
TAG		tag[MAXSIZE * 2] ;
NODE	tree[10 * (MAXSIZE)] ;

int cmp (TAG ta, TAG tb)
{
	return ta.endVal < tb.endVal ;
}

void build (int node, int left, int right)
{
	tree[node].left	 = left ;
	tree[node].right = right ;
	// 0 表示当前区间的海报数量不确定，正整数则表示当前区间完全被某海报覆盖
	tree[node].id	 = 0 ;

	if (tree[node].left == tree[node].right)
		return ;

	int mid = (left + right) / 2 ;
	build (L(node), left, mid) ;
	build (R(node), mid + 1, right) ;
}

void update (int node, int left, int right, int id)
{
	// 若新的海报可以覆盖当前区间
	if (left <= tree[node].left && tree[node].right <= right)
	{
		tree[node].id = id ;
		return ;
	}

/*
	// [left, right] 与 node 所在区间无交集
	if (tree[node].right < left || right < tree[node].left)
		return ;
*/
	// 若当前区间已经被海报覆盖过，且新的海报只能覆盖部分区间
	if (tree[node].id > 0)
	{
		tree[L(node)].id = tree[node].id ;
		tree[R(node)].id = tree[node].id ;
		// 重新将此区间的海报数量置于不确定状态
		tree[node].id = 0 ;
	}

	// [left, right] 与 node 所在区间有交集
	int mid = (tree[node].left + tree[node].right) / 2 ;

	// [left, right] 在 node 左半区间
	if (right <= mid)
		update (L(node), left, right, id) ;
	// [left, right] 在 node 右半区间
	else if (mid < left)
		update (R(node), left, right, id) ;
	// [left, right] 在 node 两半都有, 即在 node 中部
	else
	{
		update (L(node), left, mid, id) ;
		update (R(node), mid + 1, right, id) ;
	}

	return ;
}


void count (int node)
{
	// 表示此区间只有一张编号为 id 的海报
	if (tree[node].id > 0)
	{
		// 此海报是否已经计算过
		if (flag[tree[node].id] == false)
		{
			++cnt ;
			flag[tree[node].id] = true ;
		}
		return ;
	}
	// 已经到达叶子，此节点仍为不确定状态，则退出
	if (tree[node].left == tree[node].right)
		return ;

	// 对于不确定的树，向左右两边搜索
	count (L(node)) ;
	count (R(node)) ;
}

int main ()
{
	int i, j ;
	while (scanf ("%d", &tcase) != EOF)
	{
		while (tcase--)
		{
			memset (flag, 0, sizeof (flag)) ;
			scanf ("%d", &n) ;
			for (i = 1 ; i <= n ; ++i)
			{
				scanf ("%d%d", &num[i][0], &num[i][1]) ;
				tag[2 * i - 1].id		= i ;
				tag[2 * i - 1].isLeft	= true ;
				tag[2 * i - 1].endVal	= num[i][0] ;

				tag[2 * i].id		= i ;
				tag[2 * i].isLeft	= false ;
				tag[2 * i].endVal	= num[i][1] ;
			}
			sort (tag + 1, tag + 2 * n + 1, cmp) ;

			int t = 1, tmp = tag[1].endVal ;
			for (i = 1 ; i <= 2 * n ; ++i)
			{
				// 本来以为这一句不加也没关系，结果WA了，跳过重复的值，
				if (tmp != tag[i].endVal)
				{
					tmp = tag[i].endVal ;
					++t ;
				}
				if (tag[i].isLeft == true)
					num[tag[i].id][0] = t ;
				else
					num[tag[i].id][1] = t ;
			}

			build (1, 1, 2 * n) ;

			for (i = 1 ; i <= n ; ++i)
			{
				update (1, num[i][0], num[i][1], i) ;
			}
			cnt = 0 ;
			count (1) ;
			printf ("%d\n", cnt) ;
		}
	}
	return 0 ;
}