NOIP 2025 T4 题解

提供一个 $O(nq)$ 的赛时做法。

首先考虑 $L=R$ 的情况，显然可以用单调队列维护，这启发我们对于一般的情况也用单调队列维护。

具体地，我们先预处理出前缀和 $sum_i=\sum\limits_{j=1}^ia_j$，考虑依次计算出 $i=1\sim n$ 的答案。

注意到对于右端点相同的区间，有用的左端点显然只有合法范围（$r-l+1\in[L,R]$ 且 $l\le i$）内 $sum_{l-1}$ 最小的那一个，所以维护的应该是按 $r$ 升序、$sum_r-sum_{l-1}$ 降序排列的单调队列。

为了方便我们在单调队列中维护一个二元对 $(r,w)$ 代表区间，其中 $w=sum_{l-1}$。

考虑怎么动态维护这个东西，显然我们每次将 $i$ 增加 $1$ 的时候，要做以下三个操作：

前两个操作都是容易的，但第三个操作我们不能暴力修改。

我们发现对于所有 $r<i+L-1$ 的区间，左端点都不可能再更新了。所以可以分成两个单调队列，将不能更新的放到第一个里面，还能更新的放到第二个里面（当然两个单调队列拼起来之后还要满足单调性）。

对于所有 $r\ge i+L-1$ 的区间，它们对应的左端点的合法范围是一个 $\le i$ 的后缀，所以右端点越小左端点的合法范围越大，当前的 $sum_{l-1}$ 也就越小。换句话说，第二个单调队列中的 $w$ 一定是单调不减的，所以我们更新的一定是第二个单调队列的一个后缀。

然而，这样直接暴力更新复杂度也是错的，但我们观察到第二个单调队列一定是由很多 $w$ 相等的连续段构成的，那么我们只需要用链表维护连续段，就可以做到 $O(1)$ 合并了。这样时间复杂度就是均摊 $O(nq)$ 的。

具体实现上，我赛时是用 deque 维护单调队列，手写链表，最后一个大样例 1.3s，应该不卡常。

代码等公示再放。