|
|
題目鏈接：http://poj.org/problem?id=3264
  /**//*
 題意：
給定一個長度為N(N <= 50000)的數(shù)列Si，緊接著Q(1 <= Q <= 200000)條詢問，
每次詢問給出兩個數(shù)字表示數(shù)列的區(qū)間下標，問該區(qū)間中最大數(shù)和最小數(shù)的差。
解法：
線段樹 或者 RMQ
思路：
線段樹區(qū)間最值，維護一顆完全二叉樹，每個結點保存兩個值，表示該結點管理
的區(qū)間的最大值和最小值，比如1號為根結點，管理區(qū)間[1, n]，每個結點p有左兒子
2*p和右兒子2*p+1，當區(qū)間兩端點相同時為葉子結點，如果p管理的是[a,b]那么2*p則
管理區(qū)間[a, (a+b)/2]，2*p+1管理區(qū)間[(a+b)/2+1, b]，如此一來就可以通過遞歸，
將兒子的信息傳遞給父親，直至根節(jié)點。
 */
#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;
}
|