题解

思路

设 $nxt_i$ 是 $i$ 右侧第一个比 $p_i$ 小的位置。按首个保留位置分类可达数组。令 $f_i$ 表示首个保留元素为 $p_i$ 的方案数，令 $chain_i$ 沿连续的“右侧首个更小位置”累加对应方案。

做法

从右向左处理，有

$$f_i=\sum_{j=i+1}^{nxt_i}f_j+chain_{nxt_i},\qquad chain_i=f_{nxt_i}+chain_{nxt_i}.$$

把空后缀看作位置 $n$ 的一个方案；若不存在 $nxt_i$，区间和一直取到该空方案。单调栈在线性时间内求出全部 $nxt_i$，后缀和维护区间和。

最终数组的首个保留元素必须是原数组的某个前缀最小值，因此把这些位置的 $f_i$ 相加。

递增子任务中第一个元素永远保留，其余元素可独立选择保留或删除，答案为 $2^{n-1}$。小规模可对当前保留位置集合做 BFS，枚举每次坍缩的连续段。

独立复核实现使用值域线段树寻找右侧首个更小位置，并用 Fenwick 树维护上述区间和。

复杂度

主算法每组时间复杂度 $O(n)$，空间复杂度 $O(n)$。