CF1857E Power of Points

给定 $n$ 个整数坐标点 $x_1,\dots,x_n$，它们都位于数轴上。 对于某个整数 $s$，我们构造线段 $[s,x_1]$、$[s,x_2]$、$\dots$、$[s,x_n]$。注意，如果 $x_i < s$，那么线段为 $[x_i,s]$。线段 $[a,b]$ 覆盖所有整数点 $a,a+1,a+2,\dots,b$。 我们定义点 $p$ 的“幂”为有多少条线段与坐标为 $p$ 的点相交，用 $f_p$ 表示。 你的任务是，对于每个 $s \in \{x_1,\dots,x_n\}$，计算 $\sum\limits_{p=1}^{10^9}f_p$，即所有从 $1$ 到 $10^9$ 的整数点的 $f_p$ 之和。 例如，若初始坐标为 $[1,2,5,7,1]$，选择 $s=5$，则线段为：$[1,5]$、$[2,5]$、$[5,5]$、$[5,7]$、$[1,5]$。各点的幂为：$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$。它们的和为 $2+3+3+3+5+1+1=18$。

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），表示点的数量。 第二行包含 $n$ 个整数 $x_1,x_2,\dots,x_n$（$1 \le x_i \le 10^9$），表示这些点的坐标。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示当 $s=x_i$ 时所有点幂的总和。

在第一个测试用例中，我们首先选择 $s=x_1=1$，则形成的线段为：$[1,1]$、$[1,4]$、$[1,3]$。 各点的幂为：$f_1=3, f_2=2, f_3=2, f_4=1, f_5=0,\dots$。所有点幂的和为 $3+2+2+1+0+\dots+0=8$。 然后选择 $s=x_2=4$，线段为：$[1,4]$、$[4,4]$、$[3,4]$，各点幂为 $f_1=1, f_2=1, f_3=2, f_4=3$。 最后选择 $s=x_3=3$，线段为：$[1,3]$、$[3,4]$、$[3,3]$，各点幂为 $f_1=1, f_2=1, f_3=3, f_4=1$。 由 ChatGPT 4.1 翻译