【线段树 + 详细注释】北大 poj 3264 Balanced Lineup

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

    URL   : http://poj.org/problem?id=3264
    Name  : 3264 Balanced Lineup

    Date  : Saturday, October 1, 2011
    Time Stage : more than one hour 

    Result: 
9381120	panyanyany
3264
Accepted	2208K	1860MS	C++
2677B	2011-10-01 19:56:56

Test Data :

Review :
呃，修改了一下，提交，AC，很高兴，觉得这题其实也不太难嘛～～～，呃，然后，
看了下“英雄哪里出来”大神的代码，立刻石化，代码如此少，如此简洁，运用如此巧妙，
简直是我辈之模范啊。然后再看自己的代码，顿时没了兴趣，就好像一肥婆相比于苗条少女，
真是自惭形愧啊～～～

在此附上大神的地址：
http://www.cppblog.com/menjitianya/archive/2011/03/29/142964.html

人家把树的构建和更新整合在一起，大大减少的代码量，同时也根据线段树的特点，省去了
结构体中的 left，和 right，节省了内存空间。实在是很巧妙。
//----------------------------------------------------------------------------*/

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

#define INF		0x7f7f7f7f

#define MAXSIZE 50010

#define L(n)		((n) << 1)
#define R(n)		(((n) << 1) + 1)
#define MID(a, b)	(((a) + (b)) >> 1)
#define min(a, b)	(((a) < (b)) ? (a) : (b))
#define max(a, b)	(((a) > (b)) ? (a) : (b))

typedef struct {
	int		low, high ;
	int		left, right ;
} NODE ;

int		n, q ;
NODE	tree[MAXSIZE * 10] ;

void swap (int &lhs, int &rhs)
{
	int tmp ;
	tmp = lhs ;
	lhs = rhs ;
	rhs = tmp ;
}

void build (int node, int left, int right)
{
	tree[node].left		= left ;
	tree[node].right	= right ;
	tree[node].low		= INF ;		// 初始化的时候赋值为无限大
	tree[node].high		= -INF ;	// 初始化的时候赋值为无穷小

	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 pos, int x)
{
	// 到达叶子
	if (tree[node].left == tree[node].right && tree[node].left == pos)
	{
		tree[node].low = tree[node].high = x ;
		return ;
	}

	int mid = MID (tree[node].left, tree[node].right) ;

	// 当前最大值、最小值与新值进行比较，若有可能，则更新最大值 或 最小值
	tree[node].low = min (tree[node].low, x) ;
	tree[node].high = max (tree[node].high, x) ;

	// 若该点在当前区间左半部
	if (pos <= mid)
		update (L(node), left, mid, pos, x) ;
	// 若该点在右半区间
	else if (mid < pos)
		update (R(node), mid + 1, right, pos, x) ;
}

void query (int node, int left, int right, int *x, int *y)
{
	// 查找区间正好是当前区间
	// *x 为当前区间的最小值，*y 为当前区间的最大值
	if (tree[node].left == left && tree[node].right == right)
	{
		*x = tree[node].low ;
		*y = tree[node].high ;
		return ;
	}
	int mid = MID (tree[node].left, tree[node].right) ;
	int x1, y1, x2, y2 ;

	// 若所查找区间在当前区间的左半部
	if (right <= mid)
	{
		query (L(node), left, right, &x1, &y1) ;
		*x = x1 ;
		*y = y1 ;
	}
	// 若所查找区间在当前区间的右半部
	else if (mid < left)
	{
		query (R(node), left, right, &x2, &y2) ;
		*x = x2 ;
		*y = y2 ;
	}
	// 若所查找区间 横跨 当前区间的中部
	else
	{
		query (L(node), left, mid, &x1, &y1) ;
		query (R(node), mid + 1, right, &x2, &y2) ;

		*x = min (x1, x2) ;
		*y = max (y1, y2) ;
	}

	return ;
}

int main ()
{
	int	i, j ;
	int x, y, low, high ;
	while (scanf ("%d%d", &n, &q) != EOF)
	{
		build (1, 1, n) ;
		for (i = 1 ; i <= n ; ++i)
		{
			scanf ("%d", &x) ;
			update (1, 1, i, i, x) ;
		}

		for (i = 1 ; i <= q ; ++i)
		{
			scanf ("%d%d", &x, &y) ;
			if (x > y)
				swap (x, y) ;
			query (1, x, y, &low, &high) ;
			printf ("%d\n", high - low) ;
		}
	}
	return 0 ;
}