Number Line Segments Power Sum - Calculate the Sum of Segment Intersections

{ "title": "Number Line Segments Power Sum - Calculate the Sum of Segment Intersections", "description": "Given a set of points on a number line, calculate the sum of the power of each point for different segment starting points. The power of a point is the number of segments that intersect it. This problem involves calculating segment intersections and efficiently summing the power values for each point. Find the optimal solution for efficient calculation.", "keywords": "number line, segments, power, intersection, sum, algorithm, optimization, c++, coding, programming, competitive programming, problem solving", "content": "You are given n points with integer coordinates x1,…xn, which lie on a number line.\n\nFor some integer s, we construct segments [s,x1], [s,x2], …, [s,xn]. Note that if xi<s, then the segment will look like [xi,s]. The segment [a,b] covers all integer points a,a+1,a+2,…,b.\n\nWe define the power of a point p as the number of segments that intersect the point with coordinate p, denoted as fp.\n\nYour task is to compute ∑p=1109fp for each s∈{x1,…,xn}, i.e., the sum of fp for all integer points from 1 to 109.\n\nFor 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: f1=2,f2=3,f3=3,f4=3,f5=5,f6=1,f7=1,f8=0,…,f109=0. Their sum is 2+3+3+3+5+1+1=18.\n\nInput\nThe first line contains an integer t (1≤t≤104) — the number of test cases.\n\nThe first line of each test case contains an integer n (1≤n≤2⋅105) — the number of points.\n\nThe second line contains n integers x1,x2…xn (1≤xi≤109) — the coordinates of the points.\n\nIt is guaranteed that the sum of the values of n over all test cases does not exceed 2⋅105.\n\nOutput\nFor each test case, output n integers, where the i-th integer is equal to the sum of the powers of all points for s=xi.\n\nc++代码内容：c++\n#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <map>\nusing namespace std;\n\nint main() {\n int t;\n cin >> t;\n while (t--) {\n int n;\n cin >> n;\n vector<int> points(n);\n map<int, int> count;\n for (int i = 0; i < n; i++) {\n cin >> points[i];\n count[points[i]]++;\n }\n vector<int> powers(n);\n for (int i = 0; i < n; i++) {\n powers[i] = count[points[i]];\n }\n for (int i = 0; i < n; i++) {\n int s = points[i];\n long long sum = 0;\n for (int j = 1; j <= 109; j++) {\n if (j >= s) {\n sum += powers[j];\n } else {\n sum += count[j];\n }\n }\n cout << sum << " ";\n }\n cout << endl;\n }\n return 0;\n}\n