单调栈

单调栈接触挺久了，一直没有仔细研究。
昨天模拟赛，一道单调栈没有看出来。
现在认真学学！

对于这道题，因为它是连续子序列
所以我们可以统计每一个值的贡献
即，(作为最大值的次数-作为最小值的次数)*高度

如何求作为最大值的次数？
我们可以求解，向左走第一个比他大的索引，向右走第一个比他大的索引
那么，在这个区间内。他就是最大值！
利用单调栈可以很容易地统计出来！

然后我们可以用同样的方法统计出最小值的次数

但是哇，我们这样有一个bug
就是，这个区间内有重复的数，我们统计时可能会有区间被重复选取！
那么该怎么办呢？

学到了！
我们可以在单调栈判断时，对于左边我们取等，对于右边我们不取等！
真的巧妙！

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int max_n = 1e6+100;
const int inf = 1e9;
int h[max_n],lft[max_n],rgt[max_n];
int n;

int main(){
    ios::sync_with_stdio(0);
    while (cin>>n){
        for (int i=1;i<=n;++i)cin>>h[i];
        vector<int> stack;
        stack.push_back(0);
        h[n+1]=h[0]=inf;
        for (int i=1;i<=n;++i){
            while (h[stack.back()]<=h[i])stack.pop_back();
            lft[i]=i-stack.back();
            stack.push_back(i);
        }
        stack.clear();
        stack.push_back(n+1);
        for (int i=n;i>=1;--i){
            while (h[stack.back()]<h[i])stack.pop_back();
            rgt[i]=stack.back()-i;
            stack.push_back(i);
        }
        ll ans = 0;
        for (int i=1;i<=n;++i)ans+=1LL*lft[i]*1LL*rgt[i]*1LL*h[i];
        stack.clear();
        h[0]=h[n+1]=0;
        stack.push_back(0);
        for (int i=1;i<=n;++i){
            while (h[stack.back()]>=h[i])stack.pop_back();
            lft[i]=i-stack.back();
            stack.push_back(i);
        }
        stack.clear();
        stack.push_back(n+1);
        for (int i=n;i>=1;--i){
            while (h[stack.back()]>h[i])stack.pop_back();
            rgt[i]=stack.back()-i;
            stack.push_back(i);
        }
        for (int i=1;i<=n;++i)ans-=1LL*lft[i]*1LL*rgt[i]*1LL*h[i];
        cout<<ans<<endl;
    }
}