题意

对于一个正整数序列 $a_{1 \ldots n}$ 的一个严格上升子序列 $a_{i_1},a_{i_2}, \ldots ,a_{i_k}$ 权值为存在 $p > i_k$ 且 $a_p>a_j$ 的 $j\in i$ 的数量。求所有严格上升子序列权值和。($2 \times 10^5$)

Solution

以下上升子序列均表达为子序列。

首先套路的转换为统计对于一个位置 $j$ ，有多少个包含它的能造成贡献的子序列。

找到最大的 $p$ 满足 $a_p>a_j$，则能造成贡献的子序列满足 $i_k<p$。

正向统计不好统计考虑正难则反，统计包含 $j$ 的满足 $i_k \ge p$ 的子序列。

首先包含 $j$ 的上升子序列个数为 以 j 为终点的子序列数 $\times$ 以 j 为起点的子序列数。

由于 $p$ 是最大的 $a_p>a_j$ 的位置，若存在更大的 $p'>p$ 也满足 $a_p'>a_j$，则 $p$ 不是最大位置。也就是说，不存在 $i_k > p$ 的子序列，只可能存在 $i_k = p$ 的子序列。

综上，不合法的子序列个数为包含 $j$ 且以 $p$ 为终点的子序列个数，倒序转移时只选择 $i'>i$ 且 $a_i' \in [a_i+1,a_p-1]$ 的位置转移，再加上 $p$ 位置的转移，注意这里的 $p$ 是对于 $i$ 的最大位置。

总结一下，我们要统计后缀最大位置，以及以某个点为起点/终点，以及限定转移点值域的以某个点为起点的子序列个数，这些都可以用树状数组维护。复杂度 $O(nlogn)$。

code