HDU 5443 Sparse Table（ST表模板）

        ST 表，O( nlogn ) 建表， O( 1 ) 查询最值    HUD 5443

#include<bits/stdc++.h>
using namespace std;

const int SIZE = (int)1E6 + 8;
int ST_table[SIZE][27];
int Pow[SIZE];

void getPow() {
	for (int pos = 1; pos <= SIZE; pos++) {
		int P = 0;
		while (1 << (P + 1) <= pos) P++;
		Pow[pos] = P;
	}
}

void RMQ_init(int total) {
	for (int base = 1; (1 << base) <= total; base++)
		for (int pos = 1; pos + (1 << base) - 1 <= total; pos++)
			ST_table[pos][base] = 
			max(ST_table[pos][base - 1], ST_table[pos + (1 << (base - 1))][base - 1]);
}

int RMQ(int L, int R) {
	int P = Pow[R - L + 1];
	return max(ST_table[L][P], ST_table[R - (1 << P) + 1][P]);
}

int main() {
	int quan; scanf("%d", &quan); getPow();
	while (quan--) {
		int total, que;
		scanf("%d", &total);
		for (int pos = 1; pos <= total; pos++)
			scanf("%d", &ST_table[pos][0]);
			
		scanf("%d", &que);
		int L, R; RMQ_init(total);
		while (que--) {
			scanf("%d%d", &L, &R);
			printf("%d\n", RMQ(L, R));
		}
	}
}