description
长度为 \(n\) 的序列 \(a\) 的一个严格上升子序列的权值为该子序列中严格比序列 \(a\) 中该子序列右边最大值小的数的个数，求序列 \(a\) 的所有严格上升子序列的权值和。
\(n\leq 2\times 10^5\)
solution
离散化。
先转化成对每个数 \(a_i\) 算贡献，计算以 \(a_i\) 为起点有多少个严格上升子序列满足该子序列的最大值在 \(a\) 中所在位置的右边还有比 \(a_i\) 严格大的数。再乘上以 \(a_i\) 为终点的严格上升子序列个数，这个可以树状数组优化 dp，\(O(n\log n)\)。
下面主要考虑如何计算以 \(a_i\) 为起点的满足最大值右侧存在比 \(a_i\) 大的数的严格上升子序列的个数。
倒着暴力 dp 是 \(O(n^3)\) 的，不能接受。
考虑这样转移：
设 \(a_i\) 处的 dp 值要从 \(a_j\) 处转移过来，且 \(pos\) 是满足 \(a_{pos}>a_i\) 的最大的 \(pos\)。
-
若 \(a_j<a_{pos}\)，那么 \(a_j\) 对 \(a_i\) 的贡献就是 \(a_j\) 处的 dp 值，因为此时显然 \(a_i\) 和 \(a_j\) 的 \(pos\) 相同。
-
若 \(a_j>a_{pos}\)，那么以 \(a_j\) 为起点的所有上升子序列都合法，因为它的终点一定再 \(pos\) 前，否则就与 \(pos\) 的最大性矛盾。
因此，我们用两个树状数组分别维护 dp 值和上升子序列个数即可。
时间复杂度 \(O(n\log n)\)
本题重点在于发现转移分类讨论的性质。
code
Submission #228774204 - Codeforces
标签：CF1621G,pos,严格,序列,上升,该子,dp From： https://www.cnblogs.com/FreshOrange/p/17810288.html