思维训练懒得写代码了,感觉这种题还是思维为重。
我们显然需要考察两个东西:
- 最终序列会变成啥样。
- 每次是如何一步一步变成最终序列的。
我们先想第一个问题,显然,最终的 \(p\) 一定会是最大的那个 \(a_x\) 的 \(x\),因为将最高的改高一定不优。
优化一下更改操作,每次将一段单调不降的前缀和单调不升的后缀干掉,那么只需要处理中间的值即可。
此时部分分就起到了很关键的作用,考察第二个问题,同样可以拆分成两个问题:
- 确定 \(j\) 的情况下,如何选择 \(i, k\)。
- 如何确定选 \(j\) 的顺序。
显然,考察完第一步是不会影响到第二步的决策的,此时第一步是简单的,选择 \(j\) 两边次小的 \(a_i, a_k\) 所对应的 \(i, k\) 即可。
本题的难点就在考察第二步。
我们仔细思考,发现一定先操作最小值,再操作最大值,否则 \(a_i, a_k\) 就可能会变得更大,影响到了整体的决策。一步一步想到这里,接下来的部分就是简单的了,我们只需要再次考察最小值之间的操作顺序即可,发现为了使得 \(a_i, a_k\) 尽量的小,我们一定是先操作最旁边的两个,中间的随便操作贡献就是一样的,只需要分类讨论一下是先操作左边还是右边即可。
具体过程可以用 set 和主席树维护。