题解：P13968 [VKOSHP 2024] Classics

yanxu_cn · 2025-09-04 21:14:55 · 题解

本题解主要讲一讲思路。代码写的比较烂，就不发出来了。

我们容易发现，本题中要我们求的 LIS，本质上就是每次修改对应的实际下标（在全部插入完成后的下标）的 LIS，这是由题目给定的“每次插入的数依次增大决定的”（思考：每次插入的数在增大，如果对应的下标也在增大，则就是在同一个上升子序列中的，应该比较好理解）。

然后的话就是处理这个实际下标的一个问题。这个显然可以使用树状数组、线段树、FHQ-Treap 或者一些奇技淫巧处理的。这个也是挺板的。

处理完下标标记的问题之后直接用 O(n\log n) 的贪心单调栈做法求 LIS 即可，注意到处理到每一个元素的时候得到的区间最大值就是要求的答案，输出即可。

总结：树状数组 + LIS 的拼合题目。

复杂度：时间 O(n\log n)，空间 O(n)。思考清楚则不难。