AcWing 1270. 数列区间最大值
原题链接
简单
作者:
史一帆
,
2022-01-04 14:17:08
,
所有人可见
,
阅读 206
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int f_max[N][20];
int h[N];
int n, m;
void ST_create()
{
for (int i = 1; i <= N; i ++ )
f_max[i][0] = h[i];
int k = log2(N);
for (int j = 1; j <= k; j ++ )
for (int i = 1; i <= N - (1 << j) + 1; i ++ )
f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1 << (j - 1))][j - 1]);
}
int RMQ(int l, int r)
{
int k = log2(r - l + 1);
int t1 = max(f_max[l][k], f_max[r - (1 << k) + 1][k]);
return t1;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> h[i];
ST_create();
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", RMQ(l, r));
}
return 0;
}