F - Double Sum
题意简述
Just it.
思路1
发现很像求正序对，但是需要具体数字计算。
只考虑 \(A_j-A_i>0\)，那么我们把 \(A_j,-A_i\) 分开计算。
考虑 \(A_j\) 被计算的清形，其实就是以它结尾的正序对个数。
考虑 \(-A_i\) 被计算的清形，其实就是以它开头的正序对个数，翻转序列，转化为以它结尾的逆序对个数。
离散化+树状数组经典做法，复杂度 \(O(n\log n)\)。
https://atcoder.jp/contests/abc351/submissions/52981274
思路2
其实就是求每个数 \(x\) 后面比它大的数的总和 \(sum\) 与个数 \(cnt\)（\(sum-xcnt\)）。
考虑倒着插入，然后 fhq-treap 每个节点维护权值和与 size。
查的时候直接分裂出一个 \(>x\) 的就可以了。
复杂度 \(O(n\log n)\)，常数比树状数组大得多。
还是这个思路，也可以用树状数组，一个只统计个数，一个统计权值和，和思路1的效率差不多。
平衡树：https://atcoder.jp/contests/abc351/submissions/52879648
树状数组：https://atcoder.jp/contests/abc351/submissions/52981600
标签：树状,个数,abc351,https,contests,submissions,ABC351F From： https://www.cnblogs.com/wscqwq/p/18169020