【模板】ST表

发表于

【模板】ST表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
int logn[100005],f[100005][30];//从i开始到i+2^j的最大值
int n,m;
int build_ST(int x,int y) {
	for(int j=1; j<=25; j++)
		for(int i=1; i+(1<<j)-1<=n; i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int rmq(int l,int r) { //k为区间长度
	int k=log2(r-l+1);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)scanf("%d",&f[i][0]);;
	build_ST(1,n);
	for(int i=1; i<=m; i++) {
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",rmq(l,r));
	}
}