题解：AT_abc351_f [ABC351F] Double Sum

__ryp__ · 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 的数的和以及数量即可。

可以用离散化 + 树状数组，也可以平衡树。我写的后者。

submission

upd 2024.05.02 加了一个树状数组写法