CF1913D Array Collapse 笔记

对于 $a_i$，如果选择 $[i,j]$ 满足 $a_j>a_i$ 将 $a_i$ 删去，那么 $[i,j]$ 中所有小于 $a_i$ 的数都会被删去，去除一个区间内全部大 / 小于某个数的数，考虑笛卡尔树。

当递归到笛卡尔树的 $u$ 点时，大于 $a_u$ 的数都是祖先，小于 $a_u$ 的数都是子树，如果选择 $a_u$ 左侧的祖先删去 $a_u$，那么只能保留 $a_u$ 的右子树，反之同理。

考虑 DP，设 $f_u$ 表示考虑在 $u$ 及其子树中进行删除的方案数（考虑删空），通过递归时记录两个状态，即可判断 $u$ 是否有左侧的祖先和右侧的祖先。

• 保留 $u$：$f_u\leftarrow f_{\mathrm{ls}}\times f_{\mathrm{rs}}$。
• 不保留 $u$：
  • 有左侧祖先：$f_u\leftarrow f_{\mathrm{rs}}$。
  • 有右侧祖先：$f_u\leftarrow f_{\mathrm{ls}}$。
  • $u$ 子树全部删空可能会被统计两次，若同时有左右侧祖先，应当 $-1$。

时空复杂度 $O(n)$。