原题链接：https://loj.ac/p/6490

NOIP2025T4前25分：P14638

题目描述

给定长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$，以及两个整数 $L, R$。

对于每个 $i \in [1, n] \cap \mathbb{Z}$，定义：

$$f_i = \max_{\substack{1 \le x \le i \le y \\ L \le y - x + 1 \le R}} \sum_{k=x}^{y} a_k$$

即：对于每个位置 $i$，求所有包含 $i$ 且长度在 $[L, R]$ 之间的子段中，和的最大值。

数据范围：$1 \le n, L, R \le 10^5$，$1 \le |a_i| \le 10^5$。

---

算法思路

基础转化

首先做前缀和：

$$sum[i] = \sum_{k=1}^{i} a_k$$

那么子段 $[x, y]$ 的和可以表示为 $sum[y] - sum[x-1]$。

为了快速查询任意区间内前缀和的最大值或最小值，使用 ST 表 进行 $O(1)$ 的区间最值查询。

---

核心思想：分治

本题若直接枚举，复杂度无法接受，且数列中含有负数，不具有单调性。

当枚举遇到瓶颈时，可以尝试往分治方向思考。

假设当前处理的区间为 $[l, r]$，分治函数为 solve(l, r)：

1. 若 $l = r$，则当 $L = 1$ 时，$f_l = \max(f_l, a_l)$。
2. 否则，令 $mid = \lfloor (l + r) / 2 \rfloor$，递归处理：
   • solve(l, mid)
   • solve(mid + 1, r)
3. 然后计算跨越中点 $mid$ 的区间对答案的贡献。

---

跨中区间贡献计算

左半部分（区间左端点在 $[l, mid]$）

对于每个左端点 $i \in [l, mid]$：

• 区间右端点 $y$ 必须满足 $y \in [mid+1, r]$，同时长度限制 $L \le y - i + 1 \le R$。
• 因此 $y$ 的取值范围为：

$$y \in [\max(i + L - 1,\ mid + 1),\ \min(i + R - 1,\ r)]$$

• 我们需要在 $y$ 的这个取值范围内，最大化 $sum[y] - sum[i-1]$。
• 由于 $sum[i-1]$ 是定值，只需查询 $sum[y]$ 在对应区间内的最大值。
• 用变量 pre 记录当前扫到的最大值：

pre = max(pre, ST::RMQmax(max(i + L - 1, mid + 1), min(i + R - 1, r)) - sum[i - 1]);
f[i] = max(f[i], pre);

这样强制让右端点在 $[mid+1, r]$ 内，确保区间跨越了中点，同时覆盖了 $[i, mid]$ 中的所有数，不会造成错误的更新。

右半部分（区间右端点在 $[mid+1, r]$）

对称地，对于每个右端点 $i \in [mid+1, r]$：

• 区间左端点 $x$ 必须满足 $x \in [l, mid]$，且 $L \le i - x + 1 \le R$。
• 因此 $x$ 的取值范围为：

$$x \in [\max(i - R + 1,\ l),\ \min(i - L + 1,\ mid)]$$

• 我们需要最大化 $sum[i] - sum[x-1]$，即最小化 $sum[x-1]$。
• 查询 $sum$ 在对应区间内的最小值，用变量 suf 记录：

suf = max(suf, sum[i] - ST::RMQmin(max(i - R + 1, l) - 1, min(i - L + 1, mid) - 1));
f[i] = max(f[i], suf);

---

正确性说明

分治保证了所有可能的区间都会被考虑到：

• 完全在左半部分的区间由 solve(l, mid) 处理；
• 完全在右半部分的区间由 solve(mid+1, r) 处理；
• 跨越中点的区间由上述跨中计算处理。

三者并集覆盖了所有包含任意位置 $i$ 的合法区间，因此不会有任何一种最优解被漏算。

---

复杂度分析

• 分治每层 $O(n)$，共 $O(\log n)$ 层。
• 每次查询 ST 表为 $O(1)$。

总时间复杂度：$O(n \log n)$。

空间复杂度：$O(n \log n)$（ST 表）。

---

参考代码

#include <bits/stdc++.h>
typedef long long ll;
const ll INF = 1e18;
const int maxn = 1e5 + 5;

int n, L, R;
ll a[maxn], sum[maxn], f[maxn];

namespace ST {
    int lg[maxn];
    ll mx[maxn][20], mn[maxn][20];

    void init() {
        for (int i = 0; i <= n; ++i)
            mx[i][0] = mn[i][0] = sum[i];
        for (int i = 2; i <= n + 1; ++i)
            lg[i] = lg[i >> 1] + 1;
        for (int k = 1; (1 << k) <= n; ++k) {
            for (int i = 0; i + (1 << k) - 1 <= n; ++i) {
                mx[i][k] = std::max(mx[i][k - 1], mx[i + (1 << (k - 1))][k - 1]);
                mn[i][k] = std::min(mn[i][k - 1], mn[i + (1 << (k - 1))][k - 1]);
            }
        }
    }

    ll RMQmax(int l, int r) {
        if (l > r) return -INF;
        int k = lg[r - l + 1];
        return std::max(mx[l][k], mx[r - (1 << k) + 1][k]);
    }

    ll RMQmin(int l, int r) {
        if (l > r) return INF;
        int k = lg[r - l + 1];
        return std::min(mn[l][k], mn[r - (1 << k) + 1][k]);
    }
}

void solve(int l, int r) {
    if (r - l + 1 < L) return;
    if (l == r) {
        if (L == 1) f[l] = std::max(f[l], (ll)a[l]);
        return;
    }
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid + 1, r);

    ll pre = -INF, suf = -INF;

    // 左半部分：枚举左端点 i
    for (int i = l; i <= mid; ++i) {
        int x = i + L - 1;
        int y = i + R - 1;
        pre = std::max(pre, ST::RMQmax(std::max(x, mid + 1), std::min(y, r)) - sum[i - 1]);
        f[i] = std::max(f[i], pre);
    }

    // 右半部分：枚举右端点 i
    for (int i = r; i > mid; --i) {
        int x = i - R + 1;
        int y = i - L + 1;
        suf = std::max(suf, sum[i] - ST::RMQmin(std::max(x, l) - 1, std::min(y, mid) - 1));
        f[i] = std::max(f[i], suf);
    }
}

int main() {
    scanf("%d %d %d", &n, &L, &R);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        sum[i] = sum[i - 1] + a[i];
        f[i] = -INF;
    }
    ST::init();
    solve(1, n);
    for (int i = 1; i <= n; ++i)
        printf("%lld ", f[i]);
    return 0;
}