难度困难

作为国王的统治者，你有一支巫师军队听你指挥。

给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：

• 巫师中 最弱 的能力值。
• 组中所有巫师的个人力量值 之和 。

请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。

子数组 是一个数组里 非空 连续子序列。

示例 1：

输入：strength = [1,3,1,2]

输出：44

解释：以下是所有连续巫师组：

• [1] ，总力量值为 min ([1]) * sum ([1]) = 1 * 1 = 1
• [3] ，总力量值为 min ([3]) * sum ([3]) = 3 * 3 = 9
• [1] ，总力量值为 min ([1]) * sum ([1]) = 1 * 1 = 1
• [2] ，总力量值为 min ([2]) * sum ([2]) = 2 * 2 = 4
• [1,3] ，总力量值为 min ([1,3]) * sum ([1,3]) = 1 * 4 = 4
• [3,1] ，总力量值为 min ([3,1]) * sum ([3,1]) = 1 * 4 = 4
• [1,2] ，总力量值为 min ([1,2]) * sum ([1,2]) = 1 * 3 = 3
• [1,3,1] ，总力量值为 min ([1,3,1]) * sum ([1,3,1]) = 1 * 5 = 5
• [3,1,2] ，总力量值为 min ([3,1,2]) * sum ([3,1,2]) = 1 * 6 = 6
• [1,3,1,2] ，总力量值为 min ([1,3,1,2]) * sum ([1,3,1,2]) = 1 * 7 = 7

所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。

示例 2：

输入：strength = [5,4,6]

输出：213

解释：以下是所有连续巫师组：

• [5] ，总力量值为 min ([5]) * sum ([5]) = 5 * 5 = 25
• [4] ，总力量值为 min ([4]) * sum ([4]) = 4 * 4 = 16
• [6] ，总力量值为 min ([6]) * sum ([6]) = 6 * 6 = 36
• [5,4] ，总力量值为 min ([5,4]) * sum ([5,4]) = 4 * 9 = 36
• [4,6] ，总力量值为 min ([4,6]) * sum ([4,6]) = 4 * 10 = 40
• [5,4,6] ，总力量值为 min ([5,4,6]) * sum ([5,4,6]) = 4 * 15 = 60

所有力量值之和为 25 + 16 + 36 + 36 + 40 + 60 = 213 。

提示：

• 1 <= strength.length <= 10^5
• 1 <= strength[i] <= 10^9

# 贡献法 + 单调栈

可以转化为每个元素作为最小值，计算出它是哪些子数组的最小值

当前下标为 $i$​

• 设 $l$ 为左边第一个小于 $nums[i]$ 的元素下标

• 设 $r$ 为右边第一个小于等于 $nums[i]$ 的元素下标

  为什么需要小于等于 $nums[i]$ 呢？

  例如：$[71,55,82,55]$

  若小于 $i$

  • $i = 1$ 时候的其中一个子数组：$[55,82,55],[71,55,82,55]$

  • $i = 3$ 时候的其中一个子数组：$[55,82,55],[71,55,82,55]$

  重复，则结果会变大。

  若小于等于 $i$

  • $i = 1$ 时候的其中一个子数组：$[55,82],[71,55,82]$
  • $i = 3$ 时候的其中一个子数组：$[82,55]$

  则不会出现重复的子数组

此时我们知道了子数组的最大范围 $[l + 1,r-1]$，由于该范围内的最小值都相等，可以将最小值都提出来乘以子数组和的和

即：$num\times(sum_1+sum_2+\cdots+sum_n)$

所以如何计算子数组的和的和呢？

例如：此时最大范围数组 $[1,2,3,4,5,6,7]\quad,l=-1,r=7$，范围：$[l+1,r-1]=[0,6]$

求包含 $3$ （$i=2$）的子数组的和的和

$[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7]$

• $a_0=s[3]+s[4]+s[5]+s[6]+s[7]-5\times s[0]$

$[2,3],[2,3,4],[2,3,4,5],[2,3,4,5,6],[2,3,4,5,6,7]$

• $a_1=s[3]+s[4]+s[5]+s[6]+s[7]-5\times s[1]$

$[3],[3,4],[3,4,5],[3,4,5,6],[3,4,5,6,7]$

• $a_2=s[3]+s[4]+s[5]+s[6]+s[7]-5*s[2]$

可以归纳出：$s=(i-l)\times \mathop{\Sigma} \limits_{k=i+1}^{r} s[k] - (r-i)\times\mathop{\Sigma} \limits_{k=l+1}^{i} s[k]$，其中 $i$ 为当前 $num$ 下标

如何求 $s[i] + \cdots + s[j]$ 呢？

例如：$s[3]+s[4]+s[5]$

• $ss[2]=s[1]$

  $ss[3]=s[1] + s[2]$

  $ss[4]=s[1] + s[2] + s[3]$

  $ss[5]=s[1] + s[2] + s[3] + s[4]$

  $ss[6]=s[1] + s[2] + s[3] + s[4] + s[5]$

此时 $s[3]+s[4]+s[5]=ss[6]-ss[3]$

可以归纳出：$s[i] + \cdots + s[j]=ss[j+1]-ss[i]$，其中 $ss$ 为 $s$ 的前缀和数组

子数组的和的和：$s=(i-l)\times (ss[r+1]-ss[i+1])-(r-i)*(ss[i+1]-ss[l+1])$

对结果的贡献值为：$strength[i] \times s$

class Solution {

    int MOD = 1000000007;

    public int totalStrength(int[] strength) {

        int n = strength.length;

        long[] s = new long[n + 1];

        for (int i = 0; i < n; i++) {

            s[i + 1] = s[i] + strength[i];

        }

        long[] ss = new long[n + 2];

        for (int i = 1; i <= n; i++) {

            // 取模后下面相减之后结果可能为负数

            ss[i + 1] = (ss[i] + s[i]) % MOD;

        }

        Deque<Integer> st = new ArrayDeque<>();

        st.addFirst(-1);

        long ans = 0;

        for (int r = 0; r <= n; r++) {

            int x = r == n ? Integer.MIN_VALUE : strength[r];

            while (st.size() > 1 && strength[st.peekFirst()] >= x) {

                Integer i = st.pollFirst();

                Integer l = st.peekFirst();

                ans = (ans + strength[i] * ((ss[r + 1] - ss[i + 1]) * (i - l) % MOD - (ss[i + 1] - ss[l + 1]) * (r - i)) % MOD) % MOD;

            }

            st.addFirst(r);

        }

        // 防止溢出

        return (int) (ans + MOD) % MOD;

    }

}