题目描述

米小游有一天拿到了一个数组$a$，他用这个数组构造一个新数组$b$，其中$a_i$代表$b$数组中有$a_i$个$i$。例如，若$a=[2,3,1]$，那么$b=[1,1,2,2,2,3]$。 现在给定$a$数组，你需要帮米小游求出$b$数组中所有连续子数组的极差之和。由于答案可能过大，请对$10^9+7$取模。数组的极差指最大值减去最小值。

输入格式

题解：贡献法计数+前缀和

考虑第$i$个元素对结果的贡献，选择第$i$个元素对结果的贡献 $b[i]*(b[i+1]*1+b[i+2]*2+...+b[k]*(k-i))$

如果是选择第$i+1$个元素，对结果的贡献为$b[i+1]*(b[i+2]*1+b[i+3]*2+...+b[k]*(k-i-1))$

右边的差值其实就是$b[i+1]+b[i+2]+...+b[k]$

因此可以预处理一个后缀和数组来去一遍遍历，一遍计算，当然，也可以不使用后缀和数组，维护两个变量即可