我仍然在无人问津的阴雨霉湿之地 / 和着雨音 / 唱着没有听众的歌曲
题解
有一个长度为 $n$ 的序列 $a_{1 \dots n}$。你需要不断进行下列两种操作直到无法继续：
- 令当前的序列长度为 $n^{\prime}$，选择一个满足 $1 \le i < n^{\prime}$ 且 $a_i < a_{i-1}$ 的正整数 $i$ 并删除 $a_{i+1}$。
- 令当前的序列长度为 $n^{\prime}$，选择一个满足 $1 \le i < n^{\prime}$ 且 $a_i < a_{i-1}$ 的正整数 $i$ 并交换 $a_i$ 与 $a_{i+1}$。
求最后可以得到的本质不同的序列的数量。答案对 $998244353$ 取模。
$1 \le n \le 10^5,1 \le a_i \le 10^9,1.0\rm{s},512\rm{MiB}$。
事实上，最后的序列一定是单调不增的。这点容易用反证法证明：如果存在 $i$ 满足 $a_i < a_{i+1}$ 则可以继续操作，不满足终止条件。
因此，我们需要知道：最后有哪些数可以剩下来？注意到，若存在一个正整数 $j$ 满足 $j < i$ 且 $a_j < a_i$，则我们一定可以在不影响其他操作的情况下删除 $a_i$（我们只需要取最大的满足条件的 $j$，并让 $j$ 逐步靠近 $i$ 即可，如果 $[i,j]$ 之间还有其他要被删除的数可以一并删除）。
令可以被删除的数的数量为 $c$。答案似乎是 $2^c$，但这并未去重。例如，假如 $a_3=a_{10}=5$ 且 $a_3$ 和 $a_{10}$ 均可被删除，则我们的算法会认为这两者取和不取共有 $2^2=4$ 种情况，但事实上只有 “没有 $5$”，“一个 $5$”，“两个 $5$”这三种情况。
更具体地，我们设 $T$ 为 $a$ 种所有可被删除的数的下标的集合，集合 $S_x={i|i \in T,a_i=x}$，则在最终的序列中，数 $x$ 只有 $|S_x|+1$ 种可能的贡献。根据乘法原理，我们只需要把这些贡献乘在一起。综上，答案为 $\prod(|S_x|+1)$。直接开 $\rm{map}$ 统计即可。时间复杂度 $O\left(n\log n\right)$。