牛客网 223C 区区区间间间（单调栈）

题目链接：区区区间间间

题意：给出长度为n的数字序列ai，定义区间(l,r)的价值为，

请你计算出。

题解：单调栈求ai左边和右边第一个比它小的位置，需要减去ai的个数为$(R_i-i+1)*(i-L_i+1)-1$。同理再用单调栈求ai左边和右边第一个比它大的位置，加上需要加上的ai个数即可。

解释1：需要减去的ai个数为$(R_i-i+1)*(i-L_i+1)-1$。

举个例子：1 2 3 4 5，求必须包含3的区间个数，左边有3种选择：1 2；2；不选；，右边也有三种选择：4 5；4；不选；但是题目中要求区间长度至少为2，所以两边都不选的情况不能计算在内。

解释2：为什么单调栈中一个a[i]<=a[st.top()]，另一个是a[i]<a[st.top()]（>=和>也同理）。

举个例子：5 6 5。这种情况很明显只有三个区间[5 6]，[5 6 5]，[6 5]，即减去15。

但是如果直接用<=，那么每个位置对应的区间(li,ri)分别为[1,3]，[2,2]，[1,3]。减去20。可以发现[1,3]区间被减了两次，所以需要保证相等的时候一端扩展，避免重复计算。

stack：

#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+10;
typedef long long ll;
stack <int> st;
ll l[N],r[N],a[N];

int main(){
    int t;
    scanf("%d",&t);

    while(t--){
        int n;
        ll sum=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++){
            while(st.size()&&a[i]<=a[st.top()]) st.pop();
            l[i]=st.size()==0?1:st.top()+1;
            st.push(i);
        }
        while(st.size()) st.pop();
        for(int i=n;i>=1;i--){
            while(st.size()&&a[i]<a[st.top()]) st.pop();
            r[i]=st.size()==0?n:st.top()-1;
            st.push(i);
        }
        while(st.size()) st.pop();
        for(int i=1;i<=n;i++) sum-=((r[i]-i+1)*(i-l[i]+1)-1)*a[i];
        for(int i=1;i<=n;i++){
            while(st.size()&&a[i]>=a[st.top()]) st.pop();
            l[i]=st.size()==0?1:st.top()+1;
            st.push(i);
        }
        while(st.size()) st.pop();
        for(int i=n;i>=1;i--){
            while(st.size()&&a[i]>a[st.top()]) st.pop();
            r[i]=st.size()==0?n:st.top()-1;
            st.push(i);
        }
        while(st.size()) st.pop();
        for(int i=1;i<=n;i++) sum+=((r[i]-i+1)*(i-l[i]+1)-1)*a[i];
        printf("%lld
",sum);
    }

    return 0;
}