Power of Points
Contest: Codeforces Round 891 (Div. 3)
Difficulty rating: 1500
Tags: math, sortings

You are given $$$n$$$ points with integer coordinates $$$x_1,\dots x_n$$$, which lie on a number line.

For some integer $$$s$$$, we construct segments [$$$s,x_1$$$], [$$$s,x_2$$$], $$$\dots$$$, [$$$s,x_n$$$]. Note that if $$$x_i<s$$$, then the segment will look like [$$$x_i,s$$$]. The segment [$$$a, b$$$] covers all integer points $$$a, a+1, a+2, \dots, b$$$.

We define the power of a point $$$p$$$ as the number of segments that intersect the point with coordinate $$$p$$$, denoted as $$$f_p$$$.

Your task is to compute $$$\sum\limits_{p=1}^{10^9}f_p$$$ for each $$$s \in \{x_1,\dots,x_n\}$$$, i.e., the sum of $$$f_p$$$ for all integer points from $$$1$$$ to $$$10^9$$$.

For example, if the initial coordinates are $$$[1,2,5,7,1]$$$ and we choose $$$s=5$$$, then the segments will be: $$$[1,5]$$$,$$$[2,5]$$$,$$$[5,5]$$$,$$$[5,7]$$$,$$$[1,5]$$$. And the powers of the points will be: $$$f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0$$$. Their sum is $$$2+3+3+3+5+1+1=18$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of points.

The second line contains $$$n$$$ integers $$$x_1,x_2 \dots x_n$$$ ($$$1 \le x_i \le 10^9$$$) — the coordinates of the points.

It is guaranteed that the sum of the values of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ integers, where the $$$i$$$-th integer is equal to the sum of the powers of all points for $$$s=x_i$$$.

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

Note:
In the first test case we first choose $$$s=x_1=1$$$, then the following segments are formed: $$$[1,1]$$$,$$$[1,4]$$$,$$$[1,3]$$$.

The powers of the points will be as follows: $$$f_1=3, f_2=2, f_3=2, f_4=1, f_5=0 \dots$$$ The sum of powers of the points: $$$3+2+2+1+0+\dots+0=8$$$.

After that we choose $$$s=x_2=4$$$. Then there will be such segments: $$$[1,4]$$$,$$$[4,4]$$$,$$$[3,4]$$$, and powers of the points are $$$f_1=1, f_2=1, f_3=2, f_4=3$$$.

At the end we take $$$s=x_3=3$$$ and the segments look like this: $$$[1,3]$$$,$$$[3,4]$$$,$$$[3,3]$$$, the powers of the points are $$$f_1=1, f_2=1, f_3=3, f_4=1$$$.

Example input:
3
3
1 4 3
5
1 2 5 7 1
4
1 10 100 1000

Example output:
8 7 6
16 15 18 24 16
1111 1093 1093 2893

Editorial:
If we have the segments $$$[l_1,r_1],\dots,[l_n,r_n]$$$, the sum of $$$f_p$$$ is the sum of the segments' lengths. That's because a segment $$$[a,b]$$$ intersect exactly $$$b-a+1$$$ points. Now we can find the answer for fixed $$$s$$$ in $$$O(N)$$$.
How to do it more efficiently?
Let's sort the given points so that $$$x_1\le x_2\le \dots \le x_n$$$.
Processing $$$s=x_i$$$ we get that for all $$$j\le i$$$ the segments are $$$[x_j,s]$$$ and for all $$$j>i$$$ the segments are $$$[s,x_j]$$$. We need to summarize their lengths. Formally we need to calculate
$$$$$$ \sum\limits_{j=1}^{i}(s-x_j+1)+\sum\limits_{j=i+1}^{n}(x_j-s+1)= $$$$$$
$$$$$$ n+s \cdot i-\sum\limits_{j=1}^{i}x_j+\sum\limits_{j=i+1}^{n}x_j -s(n-i)= $$$$$$
$$$$$$ n+s(2\cdot i-n)-\sum\limits_{j=1}^{i}x_j+\sum\limits_{j=i+1}^{n}x_j $$$$$$
We can maintain the sum of coordinates on the prefix and suffix, and calculate this formula for fixed $$$s$$$ in $$$O(1)$$$.
The total complexity is $$$O(n\log n)$$$.