eee

Kenny

2024-09-16 15:38:27

发布于：广东

5阅读

0回复

0点赞

ST表

#include<bits/stdc++.h>
using namespace std;
int st[1145][1145], a[1145];
int n, m;
void init(){
	for(int i = 0; i <= 16; i++){
		for(int j = 1; j + (1 << i) - 1 <= n; j++){
			if(i == 0) st[i][j] = a[j];
			else{
				st[i][j] = max(st[j][i - 1], st[j + (1 << i) - 1][i - 1]);
			}
		}
	}
}
int RMQ(int l, int r){
	int len = r - l + 1;
	int d = __lg(len);
	return max(st[l][d], st[r - (1 << d) + 1][d]); 
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	init();
	while(m--){
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", RMQ(l, r))
	}
	return 0;
}