题解：P11106 [ROI 2023 Day 1] 峰值

Judgelight · 2024-10-14 19:46:51 · 题解

我们观察下面这个样例的最优方案：

1
16
7 8 9 1 15 11 5 12 13 16 3 14 2 10 6 4

观察发现，我们本质上只关心两个序列的前缀最大和前缀最小的出现情况，在图中我们用加粗的黑线标出了。

我们发现，这样的情况可以概括为我们去寻找一个断点 i，对于 1\sim i，把 \le a_i 的划分到序列 1，把 >a_i 的划分序列 2，然后对于后面的点，设 x=\max\limits_{j=1}\limits^{i}[a_j<a_i]a_j，我们把最大值不超过 x 的 LDS 划分给序列 2，把最小值至少为 x 的 LIS 划分给序列 1。

还有一种情况就是把 1\sim i 中 <a_i 的划分到序列 1，把 \ge a_i 的划分到序列 2，后面同理。

对于 1\sim i 的划分的贡献，我们用线段树维护一下前驱后继，更新即可；对于后面的贡献，我们用树状数组维护 LIS/LDS 的单点修改前后缀查询即可。