题解：P5294 [HNOI2019] 序列

· · 题解

做法 0

注意到存在一种最优解可以将整个序列划分成若干个区间，每个区间内部的 b 都一样，且为 \dfrac{\sum_{i=l}^r a_i}{r-l+1}。

因此可以设计 dp 维护这个过程，期望通过前 30\% 的数据。

做法 1

不妨贪心维护划分。发现一个划分方案如果能拆就拆是优的，因此可以直接依次扫描，贪心维护划分方案。

具体而言，维护单调栈 S。每次将 [i,i] 插入 S，若违背单调性就向下合并。

支持信息合并只需维护 siz,\sum a,\sum a^2。

单次查询 O(n)，期望通过前 50\% 的数据。

做法 2

考虑用 ds 优化此过程。我们对称的从后往前做一次，则我们想要找出现在 x 所属的区间 [l,r]，然后加上一个前缀的答案和一个后缀的答案即可。

描述出来相当于是 l-1 时的单调栈拼上 [l,r]，再拼上 r+1 后的东西仍然有单调性。

注意到合法的 r 是一段后缀，对于判定，用可持久化单调栈维护，二分满足满足 l-1 的限制时最大的 l，然后看它是否满足比 r+1 后头小。

时间复杂度 O(n\log^2 n)。