|
|
题目链接：http://poj.org/problem?id=3264
  /**//*
 题意：
给定一个长度为N(N <= 50000)的数列Si，紧接着Q(1 <= Q <= 200000)条询问，
每次询问给出两个数字表示数列的区间下标，问该区间中最大数和最小数的差。
解法：
线段树 或者 RMQ
思路：
线段树区间最值，维护一颗完全二叉树，每个结点保存两个值，表示该结点管理
的区间的最大值和最小值，比如1号为根结点，管理区间[1, n]，每个结点p有左儿子
2*p和右儿子2*p+1，当区间两端点相同时为叶子结点，如果p管理的是[a,b]那么2*p则
管理区间[a, (a+b)/2]，2*p+1管理区间[(a+b)/2+1, b]，如此一来就可以通过递归，
将儿子的信息传递给父亲，直至根节点。
 */
#include <iostream>
using namespace std;
#define maxn 50010
struct Tree  {
int Min, Max;
}T[maxn*4];
int val[maxn];
typedef int Tree_Index;
void Build(int p, int l, int r) {
  if(l == r) {
T[p].Max = T[p].Min = val[l];
return ;
 }
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
T[p].Max = T[p<<1].Max > T[p<<1|1].Max ? T[p<<1].Max : T[p<<1|1].Max;
T[p].Min = T[p<<1].Min < T[p<<1|1].Min ? T[p<<1].Min : T[p<<1|1].Min;
}
Tree_Index Query(int p, int l, int r, int a, int b, bool bMin) {
if(l == a && b == r)
return p;
int mid = (l + r) >> 1;
if(b <= mid) {
return Query(p<<1, l, mid, a, b, bMin);
}else if(mid + 1 <= a) {
return Query(p<<1|1, mid+1, r, a, b, bMin);
}else {
Tree_Index p1 = Query(p<<1, l, mid, a, mid, bMin);
Tree_Index p2 = Query(p<<1|1, mid+1, r, mid+1, b, bMin);
if(bMin) {
return T[p1].Min < T[p2].Min ? p1 : p2;
}else {
return T[p1].Max > T[p2].Max ? p1 : p2;
}
}
}
int main() {
int n, m;
int i;
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) {
scanf("%d", &val[i]);
}
Build(1, 1, n);
while(m--){
int x, y;
scanf("%d %d", &x, &y);
Tree_Index pMax = Query(1, 1, n, x, y, false);
Tree_Index pMin = Query(1, 1, n, x, y, true);
printf("%d\n", T[pMax].Max - T[pMin].Min);
}
}
return 0;
}
|