Hihocoder --- 16周 RMG

#include <iostream>
#include <cstdlib>
#include <stdio.h>
using namespace std;

int weight[1000005];
int segtree[1000005][22];

int cal_pow(int x, int y){
	if (y == 1)
		return x;
	else if (y == 0)
		return 1;
	if (y % 2 == 0){
		int temp_value = cal_pow(x, y/2);
		return temp_value * temp_value;
	}
	else{
		int temp_value = cal_pow(x, (y-1)/2);
		return temp_value * temp_value * x;
	}
}

int findmax(int len){
	int count = -1;
	while (len > 0){
		count++;
		len = (len >> 1);
	}
	return count;
}

int main(){
	int n, m, left, right, maxT;
	int len, templen;

	scanf("%d", &n);
	for (int i=1; i<=n; i++){
		scanf("%d",&weight[i]);
	}

	for (int j=0; j<=findmax(n); j++)
		for (int i=1; i<=n; i++) {
			len = cal_pow(2, j);
			if (j == 0)
				segtree[i][j] = weight[i];
			else if ((i + len/2) <= n)
				segtree[i][j] = min(segtree[i][j-1], segtree[i + len / 2][j-1]);
		}

	cin>>m;
	for (int i=0; i<m; i++){
		scanf("%d %d",&left, &right);
		len = right - left + 1;
		maxT = findmax(len);
		templen = cal_pow(2, maxT);
		printf("%d\n",min(segtree[left][maxT], segtree[right - templen + 1][maxT]));
	}

	return 0;
}