Neat Tree

题意：

n个数，每个区间的贡献为区间内最大值减最小值，问这个n个数的总贡献是多少？也就是n所能组成的所有区间的贡献值之和

题解：

我们可以用单调栈来做
第i个数对答案的贡献值为=h[i] * 作为最大值出现的次数-h[i] * 作为最小值出现的次数
求每个点贡献值的过程可以用单调栈来维护
例如求最大值的次数：
对于第i点，找到左端第一个比h[i]大的数，记其位置为L，找到右端第一个比h[i]大的数，记其位置为R，(默认第0个位置最小，第n+1个位置最大)则区间(L,R)区间内包含点i的子区间个数就是(i-L) * (R-i)
答案的贡献就是h[i] * (i-L) * (R-i)

代码：

#include<cstdio>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int l[maxn], r[maxn];
ll h[maxn];

int main(){
    int n;
    while(~scanf("%d", &n))
    {
        for(int i=1; i<=n; i++)
            scanf("%lld", &h[i]);
        stack<int> s;

        for(int i=1; i<=n; i++)
        {
            while(!s.empty() && h[i]>=h[s.top()]) s.pop();
            //注意等号问题，因为区间不要重复。
            if(s.empty())    l[i]=0;
            else    l[i]=s.top();

            s.push(i);
        }
        //--------------计算每个区间的最大值之和 
        while(!s.empty()) s.pop();

        for(int i=n; i>=1; i--)
        {
            while(!s.empty() && h[i]>h[s.top()]) s.pop();
            if(s.empty())  r[i]=n+1;
            else     r[i]=s.top();

            s.push(i);
        }

        ll maxx=0;
        for(int i=1; i<=n; i++)
            maxx+=h[i]*(i-l[i])*(r[i]-i);
        //----------计算每个区间的最小值之和 
        while(!s.empty()) s.pop();

        for(int i=1; i<=n; i++)
        {
            while(!s.empty() && h[i]<=h[s.top()]) s.pop();
            if(s.empty()) l[i]=0;
            else l[i]=s.top();
            s.push(i);
        }

        while(!s.empty()) s.pop();

        for(int i=n; i>=1; i--){
            while(!s.empty() && h[i]<h[s.top()]) s.pop();

            if(s.empty()) r[i]=n+1;
            else r[i]=s.top();
            s.push(i);
        }
        ll minn=0;
        for(int i=1; i<=n; i++)
            minn+=h[i]*(i-l[i])*(r[i]-i);

        printf("%lld\n", maxx-minn);
    }

    return 0;
}