蒟蒻MLE*2求助大佬

P1440 求m区间内的最小值

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

数组太大了吧。。。

21 \times 2000005 = 42000105

数组最大只能到 30000000


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 那线段树应该可以吧

4\times 2000005=8000020

|