题解：P12554 [UOI 2024] Queries for Subarray Beauty

题解

我们要求区间的优美值，优美值的定义是分段后每段和绝对值的最小值。所以我们得先研究最优划分方案。先在整个数组

a

上考虑。

考虑对一个最优划分方案进行调整，我们可以发现一些性质：

因为是绝对值，段明显可以分为正段和负段。
两个相邻正段或者相邻负段合并后更优，所以最优解肯定是正负段交替出现。
（除了开头和结尾位置）正段内如果有负前缀和/后缀和，那一段前缀/后缀分给相邻的负端更优。同理负段也不能有正前缀和/后缀和。也就是说每个段必定是自己区间的最大/小子段和。
进一步考虑，如果一个正段前面/后面若干个整段的和是非负的，合并进这个正段更优。负段同理。对于相邻的三段，中间一段的绝对值如果不是严格大于旁边两段，三段合并更优。但是对于相邻四段 $a,b,c,d$ ， $\lvert b\rvert \le \lvert c\rvert$ 时合并 $abc$ 更优， $\lvert c\rvert \le \lvert b\rvert$ 时合并 $bcd$ 更优，所以调整后的最优解不可能有四段。
综上，调整后最优解要么分一段（区间和），要么分两段（分界点在前缀最大值或者前缀最小值），要么分三段且中间一段绝对值严格最大。只需要考虑这几种情况。

分一段和两段都容易维护，考虑三段的最优方案怎么算。负正负和正负正两种情况对称，我们接下来不妨只讨论正负正的分段。

可能的一个错误思路是直接找最大/最小前缀/后缀和作为分界点，但这不对。例如 $-2,9,-8,9,-2$ 就是一个反例，最优划分是 $[-2,9][-8][9,-2]$ 。

因为三段方案中间一段绝对值严格最大（否则不如合成一段），实际上三段方案的权值等于第一段和最后一段的和的较小值。如果我们枚举中间的分界位置

i

保证第二段必须跨过

i

，可以发现（并证明）第一段和最后一段必须分别是

i

前面的最大前缀和以及后面的最大后缀和，设这两个值为

pre[i]=\max_{j=0}^i (\sum_{k=1}^j a[k]),suf[i]=\max_{j=i}^n (\sum_{k=j+1}^n a[k])

。

引理. 要么

\max_{i=0}^n \min(pre[i],suf[i])

等于序列

a

划分成正负正的三段方案的最优权值，要么这个值仍然不优于分一段的方案。

证：只有一种情况可能出问题，即某个

i

高估了方案权值（

\min(pre[i],suf[i])

高于真实权值），这只能是该

i

对应的划分方案的中间一段是绝对值最小的段。但如果某个

i

满足这一点，这时的

\min(pre[i],suf[i])

必然

\le \sum a

，也就是即使

\max_{i=0}^n \min(pre[i],suf[i])

有高估也不可能超过只分一段的解。

所以我们现在只要求

\max_{i=0}^n \min(pre[i],suf[i])

。按定义可得

pre[i],suf[i]

分别是单调递增，单调递减的。单调递增和递减的函数最小值最大是在它们相交（相等）的位置。这可以线段树上二分得到，从而得到解。

建一个线段树

T

维护

a

下标区间的区间和以及区间内最大/最小的前缀/后缀和，修改是经典问题，查询的时候枚举一段，两段（正负/负正分别是最大/最小前缀和位置分开），三段（正负正/负正负分别按前述方法在线段树上二分）统计最优方案即可。

线段树上二分区间内的位置也是经典问题。大致思路是先定位出查询区间对应的所有线段树节点区间，从两边向中间逐个区间考虑，每次在较小的一端合并下一个区间，最后得到二分位置在哪个线段树节点区间内，再在那个区间的线段树子树内递归二分。也有递归的写法。

复杂度：

O(n+q\log n)