全区間転倒数

解説

$i < j$かつ$A_i > A_j$となる１つのペアの解への寄与を考えます。

このペアが含まれる区間の個数は$i \times (N-j+1)$個です。

$j$を固定して考えた際、$A_i > A_j$となる$i$について、$\sum i \times (N-j+1)$が答えに加わることになります。

Fenwick treeで条件を満たす$A_i$に$i$を加算すれば$A_j$が決まれば高速に総和を求めることができます。

実装

Rust

C++