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

CommonAnts · 2025-10-18 19:33:19 · 题解

题解

思路

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