题目链接

https://ac.nowcoder.com/acm/contest/7604/D

解题思路

参考
先看看大佬的大致思路，再看我的代码讲解。

代码讲解

先扫一眼代码，再看讲解。

构建最大值/最小值区间：

大佬写的代码比较难理解，但是时间复杂度应该比这样低点。
抽丝剥茧，分离出本质，就是找第i个位置之后第一个比a[i]大的位置，将其保存在ka[i]中。
所以说，区间[i,ka[i]-1]的最大值为a[i]。
同理，找到第i个位置之后第一个比a[i]小的位置，将其保存在ki[i]中。区间[i,ki[i]-1]的最小值为a[i]。

接下来的循环

ans[i]表示区间长度为i的最终和与区间长度为i-1的最终和之差。
枚举起点位置，找到最大值最小值都不变的一段区间，让ans[L]+=最大值最小值，ans[R+1]-=最大值最小值。
每一段区间的更新，右端点都是用最大值右端点和最小值右端点最小的去更新。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],ki[N],ka[N],ans[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    //构建最大值区间
    for(int i=n;i>=1;i--) {
        int j=i+1;
        for(;j<=n;j++) 
            if(a[j]>a[i]) {ka[i]=j;break;}
        if(j==n+1) ka[i]=n+1;
    }
    //构建最小值区间
    for(int i=n;i>=1;i--) {
        int j=i+1;
        for(;j<=n;j++) 
            if(a[j]<a[i]) {ki[i]=j;break;}
        if(j==n+1) ki[i]=n+1;
    }

    for(int i=1;i<=n;i++) {
        int ma=i;//区间最大值的位置 
        int mi=i;//区间最小值的位置 
        int minL=i;//最小值区间的左端点
        int minR=ki[minL]-1;//最小值区间的右端点
        int maxL=i;//最大值区间的左端点
        int maxR=ka[maxL]-1;//最大值区间的右端点 
        while(1) {
            int L=minL-i+1,R=min(minR,maxR)-i+1;
            //差分数组赋值 
            ans[L]  +=a[mi]*a[ma];
            ans[R+1]-=a[mi]*a[ma];
            //刷新最大值区间左端点和最小值区间左端点 
            minL=maxL=min(minR,maxR)+1;
            if(minL>=n+1) break;
            //刷新最大值区间右端点和最小值区间右端点 
            if(minL>minR) mi=minL,minR=ki[minL]-1;
            if(maxL>maxR) ma=maxL,maxR=ka[maxL]-1;
        }
    }
    for (int i=1;i<=n;i++) ans[i]+=ans[i-1];//差分求和
    for (int i=1;i<=n;i++) cout<<ans[i]<<' ';

}

吐槽

太难了吧