luogu 1714

前缀和 + rmq

#include <bits/stdc++.h>

const int N = 5e5 + 10;

int Pow[30], Log[N];
int n, m;
int a[N], sum[N];
int f[N][30];

int main() {
    std:: cin >> n >> m;
    for(int i = 1; i <= n; i ++) std:: cin >> a[i];
    for(int i = 1; i <= n; i ++) a[i] += a[i - 1];
    for(int i = 0; ((Pow[i] = (1 << i)) <= n); i ++);
    Log[1] = 0;
    memset(f, 0x3f, sizeof f);
    for(int i = 2; i <= n; i ++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1; i <= n; i ++) f[i][0] = a[i];
    for(int i = 1; Pow[i] <= n; i ++)
        for(int j = 1, ti = n - Pow[i] + 1; j <= ti; j ++)
            f[j][i] = std:: min(f[j][i - 1], f[j + Pow[i - 1]][i - 1]);
    int Answer = 0;
    for(int i = 1; i <= n; i ++) {
        int l = std:: max(i - m, 1), r = i, t;
        t = Log[r - l + 1];
        Answer = std:: max(Answer, (a[i] - std:: min(f[l][t], f[r - Pow[t] + 1][t])));
    }
    std:: cout << Answer;
    return 0;
}