Luogu5871 [SEERC2018] Inversion

题意：给出一个长度为 的排列 。

建立一张无向图，若 为一组逆序对，则在 之间连一条边。

求该图的独立覆盖集数目。（独立覆盖集指即是独立集，又是覆盖集）

数据保证答案不超过 。

，时限 。

---

不难发现，独立集 上升子序列。

再思考怎样的上升子序列是覆盖集。

图中，我们选出的上升子序列为红色点，红色部分为这些点能覆盖的区域，白色区域不能覆盖，为“禁区”。

思考“禁区”内出现点意味着什么：能将该点加入到上升子序列中。

于是，覆盖集 极大上升子序列（即不再能加入任何一个数）。

---

考虑 ，设 为前 个数的极大上升子序列个数，且必选 。

有转移：

不难 转移。