51Nod-1215-数组的宽度

描述

题解

在讨论区中，夹克老师讲得十分透彻了，我也不再做那么详细赘述了，大致的分析一下，根据夹克老师的说法，用单调栈分别求出来一个数作为最大值和最小值的贡献区间，也就是说求出这个数作为最大或者最小的值时能往前往后延伸的长度，最后根据乘法原则就能求出来每个数贡献的区间数目。

先单调递减栈搞一遍，求出每一个数作为最大值所覆盖的前后范围，然后再单调递增搞一遍，求出每一个数作为最小值所覆盖的前后范围，这样就差不多了，乘法原理搞一下就可以了，对了，需要注意 long long 哦。

代码

#include <iostream>
#include <stack>

using namespace std;

const int MAXN = 5e4 + 10;

struct num
{
    long long value;
    int maxLeft, maxRight;
    int minLeft, minRight;

    num() : maxLeft(1), maxRight(1), minLeft(1), minRight(1) {}
} A[MAXN];

int N;
int value, key;
long long res = 0;
stack<pair<int, int> > S;

void stackClear()
{
    while (!S.empty())
    {
        S.pop();
    }
}

void getMax()
{
    stackClear();

    S.push(make_pair(A[0].value, 0));
    for (int i = 1; i < N; i++)
    {
        while (!S.empty() && S.top().first <= A[i].value)
        {
            value = S.top().first;
            key = S.top().second;
            S.pop();

            A[i].maxLeft += A[key].maxLeft;
            if (!S.empty())
            {
                A[S.top().second].maxRight += A[key].maxRight;
            }
        }
        S.push(make_pair(A[i].value, i));
    }
    while (!S.empty())
    {
        key = S.top().second;
        S.pop();
        if (!S.empty())
        {
            A[S.top().second].maxRight += A[key].maxRight;
        }
    }
}

void getMin()
{
    stackClear();

    S.push(make_pair(A[0].value, 0));
    for (int i = 1; i < N; i++)
    {
        while (!S.empty() && S.top().first >= A[i].value)
        {
            value = S.top().first;
            key = S.top().second;
            S.pop();

            A[i].minLeft += A[key].minLeft;
            if (!S.empty())
            {
                A[S.top().second].minRight += A[key].minRight;
            }
        }
        S.push(make_pair(A[i].value, i));
    }
    while (!S.empty())
    {
        key = S.top().second;
        S.pop();
        if (!S.empty())
        {
            A[S.top().second].minRight += A[key].minRight;
        }
    }
}

void solve()
{
    for (int i = 0; i < N; i++)
    {
        res += A[i].value * A[i].maxRight * A[i].maxLeft;
        res -= A[i].value * A[i].minRight * A[i].minLeft;
    }
}

int main(int argc, const char * argv[])
{
    freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &A[i].value);
    }

    getMax();
    getMin();

    solve();

    cout << res << '\n';

    return 0;
}