- 搬题人
- 比赛：feecle6418
- 排列：cdw
- 选择：p_b_p_b
- 组题人
- p_b_p_b
- 题解：别急
比赛
来源：
- Petrozavodsk Winter 2020 Day 7: Gennady Korotkevich Contest 5, Problem J
- https://qoj.ac/contest/447/problem/1431
别急
排列
来源：
- Petrozavodsk Winter 2021 Day 2: UPC Contest, Problem B
- https://qoj.ac/contest/530/problem/864
别急
选择
来源：
- Moscow Pre-Finals Workshops 2022 Day 1: Opening Contest (TOPC 2016+ Selection) A
- https://qoj.ac/contest/917/problem/3835
Tutorial by p_b_p_b.
本题的证明有一些问题，在下面用黑体标出。
无脑 $O(n^2)$ 的 dp 非常显然，可惜没什么优化空间。
不难发现一个简单的性质：对于任意一个 $k$ 的最优方案，选择的每个位置 $i$ 一定是 $i$ 所在的区间里 $p_i$ 最大的位置。
那么从简单的情况开始考虑
- $k=1$ 时显然只会选择最大值 $p_{m_1}$ 。
- $k=2$ 时会选择最大值以及 $[1,m-1]$ 的最大值 $p_{m_2}$ 或是 $[m+1,n]$ 的最大值 $p_{m_3}$ ，不妨假设选择的是 $p_{m_2}$ 。
- $k=3$ 时就会发生有趣的事情——假设 $[m+1,n]$ 的次大值是 $p_{m_4},m_4>m_3$ ，那么虽然 $p_{m_1},p_{m_3},p_{m_4}$ 也满足“选择的每个位置 $i$ 一定是 $i$ 所在的区间里 $p_i$ 最大的位置”的限制，但它一定不会优于 $p_{m_2},p_{m_1},p_{m_4}$ ，更不会优于 $p_{m_2},p_{m_1},p_{m_3}$ 。
- 这是因为，$p_{m_2},p_{m_1}$ 的组合优于 $p_{m_1},p_{m_3}$ ，而 $p_{m_4}$ 在两边的贡献相同。
简单拓展一下（打表），可以发现第二个性质：对任意一个 $k$ 和一组大小为 $k$ 的最优方案 $S$ ，存在一个大小为 $k+1$ 的最优方案 $T$ ，使得 $S\subset T$ 。证明用类似的调整法即可不会证，肯定需要用到 $x^2+ax+b$ 的性质，但不知道怎么用。
因此我们只需要在每一步贪心加入贡献最大的位置，就已经对每个 $k$ 都是最优的了。
可惜，直接实现仍然是 $O(n^2)$ 的，并且搬题人并没有想到如何把它和最朴素的暴力区分开。
因此我们需要最后一个性质：对任意 $i$ ，$1,2,\cdots,i$ 的加入顺序与 $i+1,\cdots,n$ 无关。这是因为无论是加入 $x$ 还是加入 $y$ 对 $\max(x,y)+1,\cdots,n$ 造成的影响都是相同的，因此 $\max(x,y)+1,\cdots,n$ 对 $x,y$ 的相对顺序没有影响。
于是我们可以从左往右扫，维护当前见到的前缀的加入顺序。设当前做到了第 $i$ 个元素，那么 $1,\cdots,i-1$ 的顺序已经确定为 $p_1,\cdots,p_{i-1}$ ，然后求出 $i$ 应该在什么时候加入即可。
具体地，二分一个 $k$ ，判断已经加入了 $p_1,\cdots,p_k$ 的情况下，加入 $p_{k+1}$ 和 $i$ 哪个更优。但是并不知道为什么这有可二分性。这可以用平衡树维护，复杂度 $O(n\log n)$ 。