F - Double Sum Editorial by evima
A slightly different approachThe official editorial scans the sequence from right to left, but if you process the values in ascending order, you don’t need coordinate compression. Again, two Fenwick Trees are used, but here they simply correspond to \(A\), starting from \([0, 0, 0, \dots, 0, 0]\) (with \(N\) zeros) and adding processed values as you go.
Sample Implementation (Python)
from atcoder.fenwicktree import FenwickTree
N = int(input())
A = list(map(int, input().split()))
t0 = FenwickTree(N)
t1 = FenwickTree(N)
ans = 0
for i, a in sorted(enumerate(A), key=lambda x: x[1]):
cnt = t0.sum(0, i)
tot = t1.sum(0, i)
ans += cnt * a - tot
t0.add(i, 1)
t1.add(i, a)
print(ans)
posted:
last update: