T2

题意描述

你有一个序列 $a$ 和两种操作：

1. 选择 $a_i<a_{i+1}$ 并删去 $a_{i+1}$。

2. 选择 $a_i<a_{i+1}$ 并交换这两个数。

你要不断进行这两种操作，直到无法继续，求结束时会得到多少种序列？

$1\le n\le 10^5,1\le a_i\le 10^9$。

解答

这个问题直接解决比较难，我们考虑以更好的角度切入问题。

首先考虑整个序列的最大值（可能有多个），如果在原序列里有一个极长前缀都是最大值，那么显然这些数无法移动。

对于不在这个前缀的最大值，每个数都可以独立选择删或不删。

然而由于题目的条件，最后剩下的序列显然是一个不升序列，所以实际上这些可以独立选择删或不删的数，决定的就是不升序列里这种数留下来的数量。

你又发现如果这些最大值选择不删（或者是没法删），则最后一定要挪到左边去。

所以你现在就可以把这些最大值挪过去，不然这些数会挡路。然后你就可以把这些数删去并递归了。

既然这个不升序列里每种数出现次数的决定是独立的，我们当然可以把它们乘起来。

直接用 set 模拟可以实现代码，有没有更简洁的方法？

如果一个数是前缀最小值，则它一定不可以被删去，而反之可以删去，用这个实现就好了。

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