Power of Points (Codeforces 1857E)
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: 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: 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$$$.

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$$$.

Sample Inputs:
3
3
1 4 3
5
1 2 5 7 1
4
1 10 100 1000

Sample Outputs:
8 7 6
16 15 18 24 16
1111 1093 1093 2893

Solution (Python):
num = int(input())
ans = []
for _ in range(num):
    n = int(input())
    s = sorted(enumerate(map(int, input().split())), key=lambda x: x[-1])
    a = [0 for i in range(n)]
    f = 0
    x = s[0][-1]
    for i in range(n):
        f += s[i][-1] - x + 1
    for i in range(n):
        if i == 0:
            a[s[0][0]] = f
        else:
            a[s[i][0]] = f + (s[i][-1] - x) * ((i + 1) * 2 - n - 2)
            f = a[s[i][0]]
            x = s[i][-1]
    ans.append(a)
for i in ans:
    print(' '.join(map(str, i)))

Solution (Python):
def main():
    tcn = int(input())
    for _ in range(tcn):
        n = int(input())
        nums = [int(x) for x in input().split()]
        power_of_points(n, nums)

def power_of_points(n, nums):
    snums = sorted(nums)
    hst = dict()
    s = sum(snums)
    pre = 0
    for (i, num) in enumerate(snums):
        s = s + i * (snums[i] - pre) - (n - i) * (snums[i] - pre)
        pre = num
        hst[num] = s + n
    for num in nums:
        print(hst[num], end=' ')
    print()
if __name__ == '__main__':
    main()

Solution (Python):
def compute_power(t, testcases):
    results = []
    for _ in range(t):
        (n, coordinates) = testcases[_]
        sorted_coordinates = sorted(coordinates)
        prefix_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix_sum[i] = prefix_sum[i - 1] + sorted_coordinates[i - 1]
        suffix_sum = [0] * (n + 2)
        for i in range(n, 0, -1):
            suffix_sum[i] = suffix_sum[i + 1] + sorted_coordinates[i - 1]
        coord_to_idx = {val: idx for (idx, val) in enumerate(sorted_coordinates)}
        total_power = []
        for s in coordinates:
            idx = coord_to_idx[s]
            left_sum = s * idx - prefix_sum[idx]
            right_sum = suffix_sum[idx + 1] - s * (n - idx)
            total_power.append(left_sum + right_sum + n)
        results.append(total_power)
    return results
t = int(input())
testcases = []
for _ in range(t):
    n = int(input())
    coordinates = list(map(int, input().split()))
    testcases.append((n, coordinates))
output = compute_power(t, testcases)
for result in output:
    print(' '.join(map(str, result)))