P9388 [THUPC 2023 决赛] 先人类的人类选别 笔记

考虑操作是什么：从左到右贪心选择一段下降子序列，把子序列中每一个数向后踢，并且满足子序列的第一个数 $<x$，最后的数“飞榜”。

因此考虑一段前缀 $[1,i]$，有两种情况：

• $x$ 成功踹飞了某个数，那么必然有一个数会被踹到 $i$ 以后，这个数一定是当前的 $\underset{j\in [1,i]}{min}{a}_j$。
• $x$ 没有踹飞任何数，那么说明 $x$ 比当前 $[1,i]$ 内任何数都要小。

因此，第 $k$ 次操作对于 $j\in [1,i]$ 相当于把所有 $x$ 和 $a_j$ 中的前 $k$ 小去掉。

区间前 $k$ 小使用主席树即可，但是 $x$ 是否要向每个 ${\mathrm{root}}_i$ 内更新？实则可以单独维护一个 ${\mathrm{root}}_{n+1}$ 表示所有 $x$ 的信息，查询的时候同时考虑上这个树即可。

时空复杂度 $O(n\log n+m\log m)$。