Moving Points
Contest: Codeforces Round 624 (Div. 3)
Difficulty rating: 1900
Tags: data structures, divide and conquer, implementation, sortings

There are $$$n$$$ points on a coordinate axis $$$OX$$$. The $$$i$$$-th point is located at the integer point $$$x_i$$$ and has a speed $$$v_i$$$. It is guaranteed that no two points occupy the same coordinate. All $$$n$$$ points move with the constant speed, the coordinate of the $$$i$$$-th point at the moment $$$t$$$ ($$$t$$$ can be non-integer) is calculated as $$$x_i + t \cdot v_i$$$.

Consider two points $$$i$$$ and $$$j$$$. Let $$$d(i, j)$$$ be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points $$$i$$$ and $$$j$$$ coincide at some moment, the value $$$d(i, j)$$$ will be $$$0$$$.

Your task is to calculate the value $$$\sum\limits_{1 \le i < j \le n}$$$ $$$d(i, j)$$$ (the sum of minimum distances over all pairs of points).

Input format:
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of points.

The second line of the input contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^8$$$), where $$$x_i$$$ is the initial coordinate of the $$$i$$$-th point. It is guaranteed that all $$$x_i$$$ are distinct.

The third line of the input contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$-10^8 \le v_i \le 10^8$$$), where $$$v_i$$$ is the speed of the $$$i$$$-th point.

Output format:
Print one integer — the value $$$\sum\limits_{1 \le i < j \le n}$$$ $$$d(i, j)$$$ (the sum of minimum distances over all pairs of points).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
1 3 2
-100 2 3

Example output:
3

Example input:
5
2 1 4 3 5
2 2 2 3 4

Example output:
19

Editorial:
Let's understand when two points $$$i$$$ and $$$j$$$ coincide. Let $$$x_i < x_j$$$. Then they are coincide when $$$v_i > v_j$$$. Otherwise, these two points will never coincide and the distance between them will only increase.
So, we need to consider only the initial positions of points. Let's sort all points by $$$x_i$$$ and consider them one by one from left to right. Let the $$$i$$$-th point be the rightmost in the pair of points that we want to add to the answer.
We need to find the number of points $$$j$$$ such that $$$x_j < x_i$$$ and $$$v_j \le v_i$$$ and the sum of $$$x_j$$$ for such points as well. We can do this using two BITs (Fenwick trees) if we compress coordinates (all values $$$v$$$) and do some kind of "scanline" by values $$$x$$$. Let the number of such points be $$$cnt$$$ and the sum of coordinates of such points be $$$sum$$$. Then we can increase the answer by $$$x_i \cdot cnt - sum$$$ and add our current point to the Fenwick trees (add $$$1$$$ to the position $$$v_i$$$ in the first tree and $$$x_i$$$ to the position $$$v_i$$$ in the second tree). When we want to find the number of required points and the sum of its coordinates, we just need to find the sum on the prefix two times in Fenwick trees. Note that you can use any "online" logarithmic data structure you like in this solution (such as treap and segment tree).
There is also another solution that uses pbds. Let's do the same thing, but there is one problem. Such data structure does not have "sum on prefix" function, so we have to replace it somehow. To do this, let's calculate only $$$x_i \cdot cnt$$$ part when we go from left to right. Then let's clear our structure, go among all points again but from right to left and calculate the same thing, but with the opposite sign (find the number of points $$$j$$$ such that $$$x_j > x_i$$$ and $$$v_j \ge v_i$$$). When we go from right to left, we need to decrease the answer by $$$x_i \cdot cnt$$$. It is some kind of "contribution to the sum" technique.
Time complexity: $$$O(n \log n)$$$.