CF 573 E Bear and Bowling
首先这题的主要思路是贪心。
设(Q_i)表示当前时刻(a_i)加入集合对答案的贡献。
然后贪心的过程：每次选择(Q_i)最大的，直到选完，然后答案为每一步结束后的最大值。
证明
引理： 若(i<jand a_i>a_j)，则(a_i)一定在(a_j)之前被选择。
(proof:)
假设当前时刻，应该取(a_j)，取了(a_i)然后得不到最优解了。
- 若(a_i)和(a_j)中间没有值，则将(a_j)换成(a_i)显然更优，与假设不符。
- 若(a_i)和(a_j)中间有值，则(forall k>i,a_k>a_i)（根据引理）。考虑将他们分别从两种情况中删除：当前选择了(a_i)得到的集合，当前选择了(a_j)得到的集合。然后再一次加入，显然每一个(a_k)对于(a_j)的贡献为(a_j)，对于(a_i)的贡献为(a_k)。由于(a_k>a_i>a_j)，所以选择(a_i)更优。
定理：每次选择(Q_i)最大的总能得到最优解。
(proof:)
假设最后最优解的大小为(S)。
和引理的证明类似：通过假设反证，设当前为第一个无法到达最优解的时刻。
设在加入当前的(a_i)之前的集合为(A)，根据它可以构造出的最优解集合为(B),则(Asub B)。
令(B'=complement_BA)。
可以发现(B' eq empty)，(a_i otin B')。
分两种情况：
- (B')中所有的元素都在(i)的右侧：则考虑用(a_i)替换(B')中最左边，答案不会变得更劣
- (exist kin B',k<i)，取最大的(k)，可以发现，根据引理,(a_k<a_i)，答案不会变得更劣
这样我们只需要维护(Q_i)，然后全局查询最小值就可以了。
实现方式：
1. 分块+维护凸包
可以发现我们对于(Q_i)的改动要不就是一段前缀+val，要不就是一段后缀Q[i]-=a[i]。
我们可以进行分块，然后每一块维护整体+的val，和-a[i]的数值，可以发现相当于有(n)个一次函数，形如:(y=x*(-a[i])+b)。
对(b)进行区间修改。
由于查询的(x)是递增的，所以可以不需要二分，实用two-pointers。
时间复杂度：(O(N imes sqrt N))
2. 平衡树+dp
对上述的greedy思想做一下总结可以发现，取(x)个得到的最优值是取(x+1)个得到的最优值的子集。
则设(dp_{i,j})表示前i个取了(j)个的最优值，(s_{i,j})为其方案。
则可以发现(s_{i,j}sub s_{i,j-1})。
则选择加入(a_i)的是一段后缀。
可以用平衡树维护(dp_{i,j}-dp_{i,j-1})。就可以了，每次二分找出修改开始的位置。
时间复杂度为(O(Nlog N))。
Reference: 徐翊轩的题解