POJ 3264 Balanced Lineup

解法：Segment Tree(RMQ)

セグツリやるだけ

USACOの問題。

Range Minimum QueryとRange Maximum Queryを同時に処理する。

計算量O(Q lg N).

#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
typedef pair<int,int> P;
int n,q,seg[2][121072],nn;

P query(int a,int b,int k,int l,int r){
	if(r <= a || b <= l)return P(INT_MAX,INT_MIN);

	if(a <= l && r <= b)return P(seg[0][k],seg[1][k]);
	else{
		P vl = query(a,b,k*2+1,l,(r+l)/2);
		P vr = query(a,b,k*2+2,(r+l)/2,r);
		return P(min(vl.first,vr.first),max(vl.second,vr.second));
	}
}

void update(int k,int x){
	k += nn - 1;
	seg[0][k] = x;
	seg[1][k] = x;
	while(k > 0){
		k = (k-1)/2;
		seg[0][k] = min(seg[0][k*2+1],seg[0][k*2+2]);
		seg[1][k] = max(seg[1][k*2+1],seg[1][k*2+2]);
	}
}

int main(){
	scanf("%d%d",&n,&q);
	nn = 2;
	while(nn < n)nn *= 2;
	for(int i = 0;i <= nn;i++)seg[0][i] = INT_MAX,seg[1][i] = INT_MIN;
	for(int i = 1;i <= n;i++){
		int h;
		scanf("%d",&h);
		update(i,h);
	}
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		b++;
		P ans = query(a,b,0,0,nn);
		printf("%d\n",ans.second-ans.first);
	}
	return 0;
}