这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门: http://162.105.81.212/JudgeOnline/problem?id=3264
线段树,Segment Tree。
线段树(Segment Tree)讲解: http://www.wutianqi.com/?p=1140 |
// Author: Tanky Woo
// www.wutianqi.com
// POJ 3264
// Segment, RMQ
#include
using namespace std;
const int MAX = 50001;
const int INF = 100000000;
int height[MAX];
typedef struct node{
int lc, rc, _min, _max; //左端点,右端点,区间中的最小值,最大值
}Segment;
Segment seg[3*MAX]; // 开三倍大小的空间
// u代表完全二叉树的第u个,所以第u个的左子树是第2*u个,右子树是2*u+1个
void createSeg(int u, int left, int right)
{
seg[u].lc = left;
seg[u].rc = right;
if(left == right)
{
seg[u]._min = seg[u]._max = height[left];
return;
}
int mid = (left+right)/2;
createSeg(u+u, left, mid);
createSeg(u+u+1, mid+1, right);
//求区间最小值,最大值
seg[u]._min = (seg[u+u]._minseg[u+u+1]._max? seg[u+u]._max:seg[u+u+1]._max);
}
int begin, end;
void findSeg(int u, int &min;_num, int &max;_num)
{
// 如果区间在所求范围内,给出区间的最小值,最大值
if(begin<=seg[u].lc && seg[u].rc<=end)
{
if(seg[u]._min < min_num)
min_num = seg[u]._min;
if(seg[u]._max > max_num)
max_num = seg[u]._max;
}
// 否则,缩小范围,求出相应区间的最小值,最大值
else
{
int mid = (seg[u].lc+seg[u].rc)/2;
if(mid >= begin)
findSeg(u+u, min_num, max_num); //去左区间查找
if(mid+1 <= end)
findSeg(u+u+1, min_num, max_num); //去右区间查找
}
}
int main()
{
//freopen("input.txt", "r", stdin);
int i, j, N, Q, imin, imax;
while(scanf("%d %d", &N;, &Q;) != EOF)
{
for(int i=1; i<=N; ++i)
scanf("%d", &height;[i]);
createSeg(1, 1, N);
while(Q--)
{
scanf("%d %d", &begin;, &end;);
imin = INF;
imax = -INF;
findSeg(1, imin, imax);
printf("%d\n", imax - imin);
}
}
return 0;
}