单调栈

在做这道题之前我还不知道单调栈，是看一位大佬的题解才会的。
为什么要求所有区间最大值之和-最小值之和就不详细说了，上面的题解有解释。这道题中使用的是单调递减栈，即维持栈中元素时单调递减的，如果进入一个比栈顶要大的元素，就要将栈中所有比这个元素小的栈全部弹栈。在这个过程中就可以求出一个元素的可以在多长的区间内保持最大值性。
本题的的sum和ans比较玄学，不太好解释，需要自己打草稿模拟一下
详细看代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//要用long long
int read(){
    int sum = 0;
    char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) { sum = (sum<<1)+(sum<<3)+(ch^48);ch = getchar();}
    return sum;
}//数据量大，用快读
const int N=100005;
int t,n,a[N],s[N];//s为单调递减栈,保存的是下标，单调递减指的是下标对应a数组元素的单调递减

//返回最大（小）值的和
ll solve(){
    int top = 0;//栈顶
    ll ans = 0,sum = 0;//要用long long
    //ans是最后要返回的各个区间最大（小）值的和（这个区间包括了只含一个数的区间，即多加了所有数的和，但是这并不影响最后答案的正确性，因为求最小时同样多减了所有数的和），sum是所有以当前位置为右端点的前面各个区间最大（小）值的和
    for(int i = 1;i <= n;i++){
        //如果栈不空并且单调递减栈的单调性将在i进入后被破坏，就要退栈清算sum
        while(top != 0 && a[ s[top] ] < a[i]){
            sum -= (ll)(s[top] - s[top-1]) * a[ s[top] ];//因为区间最大值被改变，所以sum要减掉之前比i小的部分贡献（不理解的话就动手模拟一下，再看一下sum的定义）
            //要转long long，不然只有70分
            top--;
        }
        s[++top] = i;//不管怎么样，i都要入栈的
        sum += (ll)(s[top] - s[top-1]) * a[ s[top] ];//s[top]其实就是i，这里这样写是为了保持和上面while循环式子的一致性（好看）
        //要转long long，不然只有70分
        ans += sum;
    }
    return ans;
}

int main(){
    t = read();
    while(t--){
        n = read();
        for(int i = 1;i <= n;i++) a[i] = read();
        ll zheng = solve();//求在所有区间最大值的和
        for(int i = 1;i <= n;i++) a[i] = -a[i];//a[i]原来都是非负实数，取负号后最大值就是原最小值
        ll fu= solve();//求在所有区间最小值的和并取了负
        cout<<fu+zheng<<endl;//最大值的和-最小值的和
    }
    return 0;
}