当前位置：首页 > news >正文
权值计算

news 2026/3/26 21:53:13
权值计算

Posted on 2026-03-01 15:31 贾普鲁登阅读(0) 评论(0) 收藏举报
H-权值计算_2026牛客寒假算法基础集训营2

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     /*
 6     伪代码意为计算对于[l,r]的数组，逐个取出元素计算其前所有不重复数的个数
 7     例：
 8     1 2 3 -> 1 + 2 + 3 = 6
 9     1 2 3 3 1 + 2 + 3 + 3 = 9
10     常见思路：计算每个元素对答案的贡献
11     例：
12     1 3 2 1 4 3
13     
14     第一个数 1 在 
15     l = 1
16     1
17     1 3
18     1 3 2
19     1 3 2 1
20     1 3 2 1 4
21     1 3 2 1 4 3
22     这六个包含它的数组中对每个单独的数的子答案均有贡献（1）
23     故对于第一个元素 1 它的贡献是 1 + 2 + 3 + 4 + 5 + 6
24     
25     第二个数 3 在 
26     l = 1
27     1 3
28     1 3 2
29     1 3 2 1
30     1 3 2 1 4
31     1 3 2 1 4 3
32     l = 2
33     3
34     3 2
35     3 2 1
36     3 2 1 4
37     3 2 1 4 3
38     贡献值为 1 + 2 + 3 + 4 + 5 + 1 + 2 + 3 + 4 + 5
39     
40     第三个数 2
41     l = 1
42     1 3 2
43     1 3 2 1
44     1 3 2 1 4
45     1 3 2 1 4 3
46     l = 2
47     3 2
48     3 2 1
49     3 2 1 4
50     3 2 1 4 3
51     l = 3
52     2
53     2 1
54     2 1 4
55     2 1 4 3
56     贡献值为 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 + 1 + 2 + 3 + 4 
57     
58     第四个数 1
59     last[1] = 1;
60     b += (4-  1)    * (1+2+3)
61           i last[1]    等差数列求和
62     l = 1
63     1 3 2 1
64     1 3 2 1 4
65     1 3 2 1 4 3
66     l = 2
67     3 2 1
68     3 2 1 4
69     3 2 1 4 3
70     l = 3
71     2 1
72     2 1 3
73     2 1 4 3
74     l = 4
75     1
76     1 3
77     1 4 3
78     贡献值为 0 + 0 + 0 + 1 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 3
79     */
80     int T,num;
81     cin >> T;
82     map<int,int> last; //存储上一个数字为num的位置<num,postion>
83     int n,a;
84     while(T--)
85     {
86         cin >> n;
87         long long b = 0,j;
88         for(int i = 1;i <= n;i++)
89         {
90             scanf("%d",&num);
91             j = last[num];
92             // (i - j) 个 从 1 到 (n - i + 1) 的 等差数列求和
93             b += (i-j)*(1+n-i+1)*(n-i+1)/2;
94             last[num] = i;
95         }
96         cout << b << endl;
97         last.clear();
98     }
99 }