[数据结构与算法]巫师的总力量和【单调栈+前缀和的前缀和】

搞懂这个题需要先搞懂P1856子数组最小乘积的最大值，关于P1856和单调栈的知识可以见上一篇关于单调栈的文章寻找下一个最大/小问题【单调栈】
此题目是leetcode294场周赛T4，题目在巫师的总力量和

• 分析题目，相比于枚举区间，我们更倾向于枚举每一个数字，然后求以他为最小值的区间的总力量值。为了知道遍历到$i$时左右端点的值，我们采用单调栈记录每一个点的左边第一个小于他的位置$left[i]$、右边第一个小于他的位置$right[i]$。那么需要计算的区间即为$[left[i]+1,right[i]?1]$.
• 在单调栈的实现中，对于位置$i$，如果他的左边没有比他小的，那么$left[i]=?1$，同理，如果右边没有比他小的，那么$right[i]=n$。
• 对于数组[1,3,1,2]，对于两个1来说，左右都没有严格比1小的数，因此计算两个1时，区间都为左端点到右端点：整个数组；造成了重复计算，为了避免重复计算，可以采取的办法是：左边取严格小于的数，右边取小于等于的数，这样就不会有重复计算的问题，同时也不会影响左右端点的值。
• 假设当前遍历到的数组的值为$x$，位置为$i$，原数组为nums，需要计算的区间即为$[left[i]+1,right[i]?1]$。令$L=left[i]+1$，$R=right[i]?1$，即问题为：对于一个区间[L,R]，需要计算所有包含了$x$的子数组的和。
• 多次计算子数组的和当然是使用前缀和的方法，前缀和数组s，第一项为0，此后为原数组的各项的和，一共n+1项。对于s[b]-s[a]，则表示${\sum }_{i=a}^{b?1}nums[i]$，即从nums[a]累加到nums[b-1]。
• 回到问题，遍历到位置为$i$的数$x$，对于区间[L,R]，假设其中一个子区间为[l,r]，其中l≤i≤r，则此子区间的和为${\sum }_{i=l}^{r}nums[i]$，即s[r+1]-s[l]。则[L,R]对整个答案的贡献为：${\sum }_{r=i+1}^{R+1}$${\sum }_{l=L}^i(s[r]?s[l])$ ，即左端点从L到i，右端点从i到R(但是前缀和的计算到R+1，且起始点为i+1)
  $$\begin{array}{rlr}res& =\sum _{r=i+1}^{R+1}\sum _{l=L}^i(s[r]?s[l])& \\ & =\sum _{r=i+1}^{R+1}[(i?L+1)?s[r]?\sum _{l=L}^{i}s[l]]& \\ & =(i?L+1)?\sum _{r=i+1}^{R+1}s[r]?\sum _{r=i+1}^{R+1}\sum _{l=L}^{i}s[l]& \\ & =(i?L+1)?\sum _{r=i+1}^{R+1}s[r]?(R?i+1)?\sum _{l=L}^{i}s[l]& \end{array}$$
• 可以看出，为了求解[L,R]对答案的贡献，还需要累加s数组，可以采取的办法同上，对s数组进行前缀和操作，设数组为ss，即原数组nums的前缀和的前缀和，第一项为0，此后为s数组的各项的和，一共n+2项。对于ss[b]-ss[a]，则表示${\sum }_{i=a}^{b?1}s[i]$，即从s[a]累加到s[b-1]。
• 因此${\sum }_{r=i+1}^{R+1}s[r]$=$ss[R+2]?ss[i+1]$，${\sum }_{l=L}^{i}s[l]$=$ss[i+1]?s[L]$。
• 因此[L,R]中对答案的贡献为：$x?res=x?[(i?L+1)?(ss[R+2]?ss[i+1])?(R?i+1)?(ss[i+1]?ss[L])]$，累加所用贡献即为答案。
  代码如下：

const int MOD=1e9+7;
int totalStrength(vector<int>& strength) {
    int n=strength.size();
    stack<int>s;
    vector<int>left(n),right(n);
    for(int i=0;i<n;i++){ //单调栈求解左边第一个严格小于的位置
        while(!s.empty()&&strength[s.top()]>=strength[i]){
            s.pop();
        }
        left[i]=s.empty()? -1:s.top();
        s.push(i);
    }
    while(!s.empty()) s.pop();
    for(int i=n-1;i>=0;i--){//单调栈求解右边第一个严格小于等于的位置
        while(!s.empty()&&strength[s.top()]>strength[i]){
            s.pop();
        }
        right[i]=s.empty()? n:s.top();
        s.push(i);
    }
    vector<long long>s1(n+1,0); //原数组的前缀和s数组
    vector<long long>ss(n+2,0); //s数组的前缀和ss数组
    for(int i=0;i<n;i++){
        s1[i+1]=(s1[i]+strength[i])%MOD;
    }
    for(int i=0;i<=n;i++){
        ss[i+1]=(s1[i]+ss[i])%MOD;
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        int L=left[i]+1;
        int R=right[i]-1;
        long long res=((i-L+1)*(ss[R+2]-ss[i+1])-(R-i+1)*(ss[i+1]-ss[L]))%MOD; //计算res的值
        ans+=strength[i]*res; //计算此区间的所有子区间的贡献值
        ans%=MOD;
    }
    return (int)(ans+MOD)%MOD; //计算res时可能有负数，防止负数溢出
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系