GDUT積み木積水(スタック)

に言及

Description

1つの辺が1つになっている積み木がたくさんあります.明ちゃん(はい、あなたは間違っていません.確かに私たちと一緒に成長している明ちゃん)は、今の雨が来たときにどれだけ水が溜まっているか知りたいと思っています.明ちゃんはまたこのように二次元が好きで、そこで彼はこの三次元の現実問題を二次元の問題に簡略化しました.雨量が無限で、積み木が水を通さない、積み木の間がシームレスにつながっているとして、この二次元の世界で、すでに置かれている積み木はどのくらいの単位の積水量がありますか?

Input

第1行は、次の試験サンプル数を示す整数T(T≦100)を含む.各試験サンプルには2行の構成がある:第1行は1つの整数N(N≦1 e 6)を含み、積み木の列数を表す.2行目はN個の整数Ai(Ai≦1 e 6)を含み、i列目の積み木の個数を表す.

Output

各サンプルは1行出力され、整数が含まれ、テーマに求められます.

Sample Input

1 11 6 2 2 4 2 0 3 4 4 5 1

Sample Output

19

構想

データ範囲は10^6であり,明らかにO(n^2)はできない.不自然に桟を思い出した.減少したスタックを維持します.現在の列がスタックの一番上の列より低い場合は、スタックに入ります.それ以外の場合は、スタックの上部が現在の列より高いまでスタックを出ます.理由は明らかで、2つの比較的高い列に対して、それらの間の低い列は明らかに役に立たない.最後に、すべての列を行った後、スタック内の要素を順次スタックから出て、それらの間の矩形面積を記録し、それらの間の格子の総数を減算することが最終的な答えです.

コード#コード#

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stack>

using namespace std;
#define LL long long

LL d[1000009], g[1000009];

int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i=0; i<n; i++)
            scanf("%d", &d[i]);

        g[0] = d[0];
        for(int i=1; i<n; i++)
            g[i] = g[i-1] + d[i];
        stack<int> s;

        LL ans = 0;
        for(int i=0; i<n; i++)
        {
            if(s.empty())
            {
                s.push(i);
                continue;
            }
            int t;
            while(!s.empty())
            {
                t = s.top();
                if(d[t] > d[i])
                    break;
                s.pop();
            }

            if(s.empty())
                ans += (i-t-1)*d[t]-(g[i-1]-g[t]);

            s.push(i);
        }
        if(!s.empty())
        {
            int i = s.top();
            s.pop();
            while(!s.empty())
            {
                int t = s.top();
                s.pop();
                ans += (i-t-1)*d[i]-(g[i-1]-g[t]);
                i = t;
            }
        }
        printf("%lld
", ans);
    }
    return 0;
}