题解：CF486E LIS of Sequence

one_last_kiss · 2025-12-05 19:41:18 · 题解

前置知识：O(n \log n) 求最长上升子序列。

求 f_i 为以 i 结尾的最长上升子序列个数， g_i 为以 i 开头的最长上升子序列个数（倒着跑一遍即可）。

令最长上升子序列的个数 d。

• 不在最长上升子序列的数，f_i+g_i-1 < d，为一类数

• 若它的 (f_i,g_i) 与某个位置相同，则它一定可以被其他位置替换，所以为二类数。

• 否则为三类数。