RMQ 部分代码

int a[50001];
int f1[50001][20], f2[50001][20];
inline void work1()
{
	for(int i = 1; i <= n; i++)
		f1[i][0] = a[i];
	for(int j = 1; (1 << j) <= n; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
			f1[i][j] = max(f1[i][j - 1], f1[i + (1 << (j - 1))][j - 1]);
}
inline int RMQ1(int l, int r)
{
	int cnt = 0;
	while((1 << (cnt + 1)) <= r - l + 1) cnt++;
	return max(f1[l][cnt], f1[r - (1 << cnt) + 1][cnt]);
}
inline void work2()
{
	for(int i = 1; i <= n; i++)
		f2[i][0] = a[i];
	for(int j = 1; (1 << j) <= n; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++)
			f2[i][j] = min(f2[i][j - 1], f2[i + (1 << (j - 1))][j - 1]);
}
inline int RMQ2(int l, int r)
{
	int cnt = 0;
	while((1 << (cnt + 1)) <= r - l + 1) cnt++;
	return min(f2[l][cnt], f2[r - (1 << cnt) + 1][cnt]);
}