题解：AT_abc351_f [ABC351F] Double Sum

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-28 09:58:14

题意明显：对每个 $i$，求 $\sum\limits_{j=i+1}^n \max (A_j - A_i, 0)$。求每个 $i$ 的答案总和。

实际上就是找使得 $A_j \gt A_i$ 且 $j \gt i$ 的所有 $A_j$ 的和。我们从后往前加入 $A_i$，那么就消掉了第二维。于是只需要统计当前所有大于 $A_i$ 的数的和以及数量即可。