72pts线段树求调
  • 板块P1714 切蛋糕
  • 楼主_hud
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/6 23:07
  • 上次更新2024/12/7 10:11:34
查看原帖
72pts线段树求调
1430250
_hud楼主2024/12/6 23:07
#include <bits/stdc++.h>
#define __init ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
#define int long long
const int MAXN = 5e5+10;
int n, m, ans, s[MAXN], a[MAXN], tr[MAXN<<2];
#define ls (u<<1)
#define rs (u<<1|1)
void build(const int u, int L, int R) {
    if(L == R) { tr[u] = s[L]; return; }
    int M = (L+R) >> 1;
    build(ls, L, M), build(rs, M+1, R);
    tr[u] = min(tr[ls], tr[rs]);
}
int query(const int u, int L, int R, int l, int r) {
    if(L > r || R < l) return LLONG_MAX;
    if(l <= L && R <= r) return tr[u];
    int M = (L+R) >> 1, vres = LLONG_MAX;
    if(l <= M) vres = min(vres, query(ls, L, M, l, r));
    if(r > M) vres = min(vres, query(rs, M+1, R, l, r));
    return vres;
}
signed main() {
    __init;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        s[i] = s[i-1] + a[i]; // 前缀和
    }
    build(1, 1, n);
    ans = s[1];
    for(int i = 2;i <= n;i++) {
        if(i-m >= 1)
            ans = max(ans, s[i]-query(1, 1, n, i-m, i-1));
        else
            ans = max(ans, s[i]-query(1, 1, n, 1, i-1));
    }
    cout << ans;
    return 0;
}
2024/12/6 23:07
加载中...