贡献度思想是什么，贡献度思想就是把对答案有贡献的区间都列出来，把对答案没贡献的区间都舍去。为什么会有对答案没贡献的区间呢，因为在这个区间里，这个数字前面有和它相同的数字，我们只需要保留前面那个区间就行。
例如：
对没有重复数字的样例1来说
序号 1 2 3 4 5
ai 1 2 3 4 5
①a1=1对答案的贡献度区间为[1,1],[1,2],[1,3],[1,4],[1,5] 有1*5个
②a2=2对答案的贡献度区间为
[1,2],[1,3],[1,4][1,5]
[2,2],[2,3],[2,4],[2,5] 有2*4个
③a3=3对答案的贡献度区间为
[1,3],[1,4],[1,5]
[2,3],[2,4],[2,5]
[3,3],[3,4],[3,5] 有3*3个
④a4=4对答案的贡献度区间为
[1,4],[1,5]
[2,4],[2,5]
[3,4],[3,5]
[4,4],[4,5] 有4*2个
⑤a5=5对答案的贡献度区间为
[1,5]
[2,5]
[3,5]
[4,5]
[5,5] 有5*1个
由样例1我们可以知道，在序列中，对ai来说，当前面没有与之相同的数的时候，那么ai对答案的贡献度区间为i*(n-i+1).
答案就是1*5*1+2*4*2+3*3*3+4*2*4+5*1*5=105.
以上就是没有重复数字时，这道题的解法。
对有重复数字的样例3来说
序号 1 2 3 4
ai 2 3 3 2
①a1=2对答案的贡献度区间为[1,1],[1,2],[1,3],[1,4] 有1*4个
②a2=3对答案的贡献度区间为
[1,2],[1,3],[1,4]
[2,2],[2,3],[2,4] 有2*3个
③a3=3对答案的贡献度区间为
[3,3],[3,4] 有1*2个 （由于第2个数字也为3，因此[1,3],[1,4] [2,3],[2,4]与上面的重复了，我们舍去）
④a4=2对答案的贡献度区间为
[2,4]
[3,4]
[4,4] 有3*1个 （由于第1个数字也为3，因此[1,4]与上面的重复了，我们舍去）
从样例3我们可以知道，我们设前面第一个与ai相同的数字的位置是pos[a[i]],那么ai的贡献度区间有(i-pos[a[i]])*(n-i+1).
那么答案就是1*4*2+2*3*3+1*2*3+3*1*2=38.
好处：
如果直接使用暴力的算法的话，时间复杂度为，避免不了求区间的情况，但如果使用求贡献度的思维去求，可以在O(n)的时间复杂度内完成
摘自原文链接：https://blog.csdn.net/qq_45328552/article/details/109023946
例题：B-Beauty Values_2022牛客国庆集训派对day6 (nowcoder.com)
标签：贡献度,数字,思想,ai,贡献,答案,区间,舍去 From： https://www.cnblogs.com/ljm-xiada/p/16757615.html