shinzanmono @ 2022-09-29 23:07:48
#include <iostream>
#define re register
using namespace std;
const int sz = 2e6 + 1;
const int lgsz = __lg(sz) + 1;
int f[lgsz][sz];
int main() {
ios::sync_with_stdio(false);
re int n, m;
cin >> n >> m;
for (re int i = 1; i <= n; i++)
cin >> f[0][i];
for (re int i = 1; i <= __lg(n); i++)
for (re int j = 1; j + (1 << i) - 1 <= n; j++)
f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
cout << "0\n";
for (re int i = 2; i <= n; i++) {
re int lg = __lg(i - max(i - m, 1));
cout << min(f[lg][max(i - m, 1)], f[lg][i - (1 << lg)]) << "\n";
}
return 0;
}
by AirQwQ @ 2022-09-30 07:09:45
数组太大了吧。。。
数组最大只能到
by AC_CSP @ 2022-09-30 07:59:22
@shinzanmono 您想没想过,这题是个单调队列?
by shinzanmono @ 2022-09-30 13:46:58
@AC_CSP 想过,WA了
by shinzanmono @ 2022-09-30 13:48:38
@Air_zyc 那线段树应该可以吧