POJ_3264 Balanced Lineup

問題
http://poj.org/problem?id=3264

解法
SegmentTree で RMQ みたいなことをする。
自力でせぐつりーを実装できるようになった。

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 1 << 29;
int n, a[100001 * 2], b[100001 * 2], q;
// a:最大値 b:最小値
void init(int _n){
	n = 1;
	while(n < _n){ n*=2; }
	for(int i = 0; i < 2 * n; i++){
		a[i] = -INF;
		b[i] = INF;
	}
}
void make(){
	for(int i = n - 2; i >= 0; i--){
		a[i] = max(a[i * 2 + 1], a[i * 2 + 2]);
		b[i] = min(b[i * 2 + 1], b[i * 2 + 2]);
	}
}
int rmq_a(int i, int j, int k, int l, int r){
	if(l <= i && j <= r) return a[k];
	if(r <= i || j <= l) return -INF;
	int ld = rmq_a(i, (i + j) / 2, k * 2 + 1, l, r);
	int rd = rmq_a((i + j) / 2, j, k * 2 + 2, l, r);
	return max(ld, rd);
}
int rmq_b(int i, int j, int k, int l, int r){
	if(l <= i && j <= r) return b[k];
	if(r <= i || j <= l) return INF;
	int ld = rmq_b(i, (i + j) / 2, k * 2 + 1, l, r);
	int rd = rmq_b((i + j) / 2, j, k * 2 + 2, l, r);
	return min(ld, rd);
}
int main(){
	int _n;
	scanf("%d %d", &_n, &q);
	init(_n);
	for(int i = 0; i < _n; i++){
		scanf("%d", &a[n - 1 + i]);
		b[n - 1 + i] = a[n - 1 + i];
	}
	make();
	for(int i = 0; i < q; i++){
		int s, g;
		scanf("%d %d", &s, &g);
		s--;
		printf("%d\n", rmq_a(0, n, 0, s, g) - rmq_b(0, n, 0, s, g));
	}
	return 0;
}