Luogu5073 [Ynoi2015] 世上最幸福的女孩

发表于 分类于 ， ， 阅读次数：

题意：全局加，区间最大子段和。

允许离线，，，时限 ，空限 。

考虑经典的维护最大子段和的线段树，需要记录下列四个值 : 最大前缀 ，最大后缀 ，最大子段和 ，区间和 。

然而，仅记录这几个值并不能支持快速打标记。

考虑改而记录成四个函数， ，分别表示该区间整体加上 后的最大前缀，最大后缀，最大子段和，区间和。

其中 显然等于 。

而 可以通过经典的转移得到 :

对于区间 ，在整体加上 之后的和会增加 ，故一个区间对函数的贡献是一条直线。

这里 都是若干候选区间取 的形式，可以用若干直线的 来描述，为下凸壳。

将直线 视作点 ，对偶后转化为维护上凸壳。

由于不同的 的数目是 的，故凸壳的大小也是 的，求个和就是 。

于是，大力求出所有的分段函数，时空复杂度均为 。

在查询时，根据全局标记，在对应区间的函数求值，并按照经典的最大子段和合并方法计算答案。

分段函数求值需要二分，这样复杂度就是 的，无法通过。

考虑离线，将全局加标记从小到大排序，这样求值就能线性扫描了。

除此之外，高达 的空间复杂度很可能导致 ，考虑优化。

将原序列分成大小为 个块，区间询问会被拆分成 个整块询问和 个零散询问，即 次函数求值，没有增加复杂度。

逐块处理即可将空间降至 。

时间复杂度 ，空间复杂度 。