題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1714 切蛋糕

Problem Statement

題目簡述

給定長度為 $n$ 的序列，每個位置有一個幸運值。
小 Z 最多只能吃 $m$ 塊蛋糕，請在所有長度至少為 $1$ 且不超過 $m$ 的連續子區間中，找出區間和的最大值。

形式化地，找一段子段 $[l,r]$ 且 $r-l+1 \le m$ ，最大化 $\sum_{i=l}^r p_i$ 。

Constraints

約束條件

$1 \le n \le 5\times 10^5$
$1 \le m \le n$
$|p_i| \le 500$
保證答案的絕對值在 $[0,2^{31}-1]$ 之內

思路：前綴和 + 滑動窗口最小值（單調佇列）

1. 從題目本質開始

本題本質上是在 P1115 最大子段和或 53. Maximum Subarray 的基礎上，加上了區間大小的限制。

回顧一下在前述題目中，我們是如何最大化一段連續區間的和的？其中一種做法是把「區間和」改寫成「兩個前綴和的差」。即令前綴和 $s[i]$ 表示前 $i$ 個元素的總和（特別地，令 $s[0]=0$ ），那麼任意區間 $[l + 1, r]$ 之和為 $s[r] - s[l]$ 。

不過本題多了一個限制：區間長度至少需要為 $1$ 且不能超過 $k$ 。換成前綴和的下標，就是：

1 \le r - l \le k

2. 固定右端點，問題變成找最小前綴和

固定 $r$ 時，想讓 $s[r] - s[l]$ 最大，就等價於在所有允許的 $l$ 中，找 $s[l]$ 最小者。

根據上述限制，允許的 $l$ 範圍是：

r - k \le l \le r - 1

所以每個 $r$ 都需要快速得到「最近 $k$ 個前綴位置內（且必須小於 $r$ ）的前綴和最小值」。這就是滑動視窗最小值問題。

關鍵結論

對每個右端點，只需要知道視窗內的最小前綴和位置，答案就是 $s[r] - \displaystyle\min_{r - k \le l \le r-1} s[l]$ 。

3. 用單調佇列維護視窗最小值

用一個雙端佇列存「候選左端點的前綴下標」，並保持它們對應的前綴和遞增：

視窗往右移時，把已經不可能再用的下標（小於 $r-k$ 的）從隊首移除。
此時隊首就是當前視窗內前綴和最小的位置，可用來更新答案。
為了維持遞增性，準備把當前前綴位置放入前，先把隊尾所有「前綴和不小於目前值」的下標移除，因為它們未來永遠不會比目前值更優。

更新順序（避免空區間）

由於區間長度至少為 $1$ ，當前右端點對應的前綴位置不能當作左端點使用。
因此流程必須是：先用既有候選左端點更新答案，再把當前前綴位置加入佇列。

複雜度分析

時間複雜度： $\mathcal{O}(n)$
空間複雜度： $\mathcal{O}(n)$

Code

from collections import deque
from itertools import accumulate


def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n

    ans = float("-inf")
    q = deque()
    s = list(accumulate(A, initial=0))
    for r, x in enumerate(s):
        # 1. 移除過期元素
        while q and q[0] < r - k:
            q.popleft()
        # 2. 更新答案
        if q:
            ans = max(ans, x - s[q[0]])
        # 3. 入隊
        while q and s[q[-1]] >= x:
            q.pop()
        q.append(r)
    print(ans)


if __name__ == "__main__":
    solve()