自动搬运

查看原文

来自洛谷，原作者为

	for_cat 为了，去码头整点薯条 | | 最后在线时间：2024年3月13日14时10分

搬运于2025-08-24 22:52:38，当前版本为作者最后更新于2024-10-10 23:51:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9877 [EC Final 2021] Vacation 题解

1.题意简述

区间长度不超过 $C$ 最大子段和。

2.前置芝士

线段树，分块。

3.题目分析

如果去掉长度小于等于 $C$ 的限制，很显然，这个题就是小白逛公园，那么我们现在的任务就要考虑如何把这个限制弱化掉。

我们首先对序列进行分块，每 $C$ 个分成一段，这样我们能得到 $\left \lceil \frac{n}{c} \right \rceil$ 个块，那么我们每次操作后的答案不是在块内，就是相邻两个块的后缀和前缀拼在一起。块内的答案相对好维护一些，大概就是小白逛公园的思路：线段树维护区间答案，区间前缀最大值，区间后缀最大值，合并的时候取左右儿子答案以及左儿子后缀最大值+右儿子前缀最大值三者中最大值即可。然后再开一个线段树维护区间整块的最值即可。

接下来，我们来考虑相邻两个块的情况。

假设我们选了两个点 $i$,$j$,那么 $i$ 和 $j$ 之间所要满足的关系是什么？

这样不太好看，我们把右边的块拿下来。

很显然如果每个块内部重新按顺序编号，那么 $j$ < $i$。

那么此时我们就可以用线段树轻松维护掉这个东西，此时线段树中每个元素的值即为前缀和，设前一个块的第i个元素的前缀和为 $a_{i}$,后一个块的第j个元素的前缀和为 $b_{j}$。

我们维护的答案即为$\operatorname*{max}_{j<i}b_{j}-a_{i}$

这个东西也很好维护：线段树维护信息即为区间答案和最大的 $b$ 和最小的 $a$,合并时区间答案即为左右区间答案和左儿子最大的 $b$ 减右儿子最小的 $a$ 三者取最值。同时再开一个线段树维护若干相邻两个块答案最值的最值。

每次查询区间答案即拆分为两个部分：1.块内的最值以及相邻两块最值的最值。2.左右两端的散块和相邻块的答案。

第一个部分可以用线段树快速查询，第二个部分我们先来看位于左端点的散块，

此时答案即为绿色部分最大值-黄色部分最小值与线段树查询黄色与蓝色答案取最大值。

右端点处散块同理，不再赘述。

然后，然后就做完了qwq。

总复杂度即为 $O(n\log n)$。