AcWing 1271. 最敏捷的机器人
原题链接
简单
作者:
史一帆
,
2022-01-04 14:22:08
,
所有人可见
,
阅读 249
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int f_max[N][20], f_min[N][20];
int h[N];
int n, k;
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]);
}
}
void 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]);
cout << t1 << ' ' << t2 << endl;
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) cin >> h[i];
ST_create();
for (int l = 1; l + k - 1 <= n; l ++ )
RMQ(l, l + k - 1);
return 0;
}