按照习惯一开始是要把题目复制一遍的，但是我想了一下，这个题目的符号复制过来会出现乱码，你说截图吧，又不想截图，那该怎么办，一时间不知道如何开始，所以就出现了上述的文字~~

绝对的好题目！！！

首先对于题目给出的公式，我们需要转化一下，我们把原式拆开就等到下面的公式
转化之后我们就求所有区间长度大于1的子区间的最大值和最小值之和。

  • 首先我们用单调栈去维护以a[i]为区间的最大值，然后往左右两边去拓展，然后我们正反跑一次单调栈就能维护出l和r数组
  • 其中l[i]表示以a[i]为最大值，左边最多延伸到l[i]，r[i]表示以a[i]为最大值，右边最多延伸到r[i]，那么如何计算呢
  • ① a[i]作为一个区间的端点，那么可以选择的区间另一个端点就是r[i]-l[i]。
    ② a[i]作为区间中的一点，也就是区间的端点都没选。那么就是在l[i]到i之间选一个作为左端点，r[i]-i之间选一个作为右端点，乘法原理可得区间的个数为 (r[i]-i) * (i-l[i])
    这样就处理出来拆分出来的和式的第一部分了。

下面我来解答一下大部分同学都会遇到的问题

  1. 第一个就是很多人不明白代码里面为什么只在一边取等号，而另一边不取等号，因为如果存在最大值有多个那么如果两边同时取就是出现重复取的情况，所以我们只要把数字放在任意一边取得就行
  2. 第二个就是如何获得最小值，因为我们知道我们跑一次单调栈求得的就是每个子区间最大值之和，所以我们就对数组每个元素取反，然后再跑一遍单调栈，得出的数中，我们取一个最大值，那么加起来就是最大值了，如果取反之后并且跑完单调栈之后最大数是负数，负数是数字越小负数越大，并且负号已经包含在里面了，直接相加就是最大值了，如果最大值是正数那么直接相加就行

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
ll a[maxn], l[maxn], r[maxn], ans, n, t;
ll solve()
{
   
    for (int i = 1; i <= n; ++i)
    {
   
        int j = i;
        while (j > 1 && a[j - 1] <= a[i])//维护左区间
            j = l[j - 1];
        l[i] = j;
    }
    for (int i = n; i >= 1; --i)
    {
   
        int j = i;
        while (j < n && a[j + 1] < a[i])//维护右区间
            j = r[j + 1];
        r[i] = j;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
   
        ans += a[i] * (r[i] - l[i]);
        ans += a[i] * (i - l[i]) * (r[i] - i);
    }
    return ans;
}
int main()
{
   
    scanf("%lld", &t);
    while (t--)
    {
   
        scanf("%lld", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%lld", &a[i]);
        ans = solve();
        for (int i = 1; i <= n; ++i)//细节操作，太强了
            a[i] = -a[i];
        printf("%lld\n", ans + solve());
    }
    return 0;
}
不管处在什么状况下的人，都应该有梦想的权利。一如我们有权选择安稳平淡的生活，也有权利为了梦想执着一次