Climb1104 @ 2024-03-09 08:27:25
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e6 + 10;
int f[N][22];
int n, m;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int min_l_r(int l, int r)
{
int k = log2(r - l + 1);
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
n = read(), m = read();
for (int i = 1; i <= n; i++)
f[i][0] = read();
// 初始化ST表
for (int j = 1; j <= 21; j++)
{
for (int i = 1; i + (1 << j) - 1 <= n; i++)
{
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 1; i <= n; i++)
{
if (i == 1)
printf("0\n");
else if (i - 1 <= m)
{
printf("%d\n", min_l_r(1, i - 1));
}
else
{
printf("%d\n", min_l_r(i - m, i - 1));
}
}
return 0;
}
by CC__DIAMOND @ 2024-03-27 17:47:45
这题很坑。虽然标签里有个RMQ,但是正常的ST会被卡内存。要过只有用单调队列。\ 可以看看P1886滑动窗口。这两题完全一样。
by Climb1104 @ 2024-03-30 17:44:28
@CC__DIAMOND 好的,谢谢
by CC__DIAMOND @ 2024-03-30 18:03:11
@Climb1104 好像这种RMQ做个滚动数组也能过?我后来在讨论区里看见一个,但是不太确定。
by Climb1104 @ 2024-03-31 08:13:24
@CC__DIAMOND 谢谢,我试一试