AcWing 1274. 奶牛排队
原题链接
简单
作者:
史一帆
,
2022-01-04 14:06:57
,
所有人可见
,
阅读 195
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e4 + 10;
int f_max[N][20], f_min[N][20];
int h[N];
int n, q;
void ST_create()
{
for (int i = 1; i <= N; i ++ )
f_max[i][0] = f_min[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]);
f_min[i][j] = min(f_min[i][j - 1], f_min[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]);
int t2 = min(f_min[l][k], f_min[r - (1 << k) + 1][k]);
return t1 - t2;
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; i ++ ) cin >> h[i];
ST_create();
while (q -- )
{
int l, r;
cin >> l >> r;
cout << RMQ(l, r) << endl;
}
return 0;
}