题解：P9877 [EC Final 2021] Vacation

· · 题解

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)。