/* 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 ;
}
分享到:
相关推荐
北大POJ3274-Gold Balanced Lineup 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1740501
北大POJ1159-Palindrome 解题报告+AC代码
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
ACM POJ 解题报告北大POJ 大量解题代码
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
北大POJ初级题-数据结构:解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1745671
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1159-Palindrome
北大POJ1837-Balance
poj 1989 The Cow Lineup.md
北大poj JAVA源码