单调栈

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

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

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

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

但是哇,我们这样有一个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;
    }
}