分治 @[遥遥领先](/user/566833)
by maokaiyu @ 2024-04-28 20:32:37
@[遥遥领先](/user/566833) 离散化+树状数组
我有个同学用了主席树……
by Big_Dinosaur @ 2024-04-28 20:32:52
倒着扫一遍，开一颗动态开点权值线段树或者离散化+树状数组，把 $a_i$ 放在数据结构中 $a_i$ 的位置。对于每个位置 $i$，先计算贡献再插入。
计算贡献时查询所有 $>a_i$ 的数的和，再减掉这些数的数量个 $a_i$ 就是位置 $i$ 对答案的贡献。对所有位置计算贡献即可。
by Shunpower @ 2024-04-28 20:38:54
thx
by 遥遥领先 @ 2024-04-28 20:57:08
@[遥遥领先](/user/566833) 不用离散化，直接树状数组就行，https://www.luogu.com/article/uo9lgxi3
by rhn7 @ 2024-04-28 22:05:19
观察到 $2 \max(a_j-a_i,0) = (a_j - a_i) + |a_j - a_i|$，于是只需要做出这场的 E 题，当然也可以选择在 E 题用 F 题做法，总之 E 和 F 是同一个题。
by quailty @ 2024-04-29 03:07:00