A16124. Power of Points
编程题
普及/提高-
知识点
题目描述
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$ .
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$ .
输入格式
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$ .
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$ .
输出格式
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$ .
输入输出样例
输入 #1
3 3 1 4 3 5 1 2 5 7 1 4 1 10 100 1000
输出 #1
8 7 6 16 15 18 24 16 1111 1093 1093 2893
说明/提示
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$ .
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$ .