stackを使うアレ

自分用メモ

N人の人が並んでいます。人はみんな左を向いているので
・自分より左にいる
・自分より背が小さい
・その人と自分の間に、自分より背が高い/同じ身長の人がいない
とき、その人の頭を見ることができます。1~N番目の人が何人の頭を見れるか求めて下さい。

当然この問題はN ^ 2で解けますがスタックを使うとNのたかだか定数倍のステップで解けます。

・（身長、k番目の人まで見れる）のペアーを積むスタックを準備
・前から配列を見る
・while(スタックが空でかつ、スタックの先頭が自分より小さい）
→　スタックの先頭を取る
→　そいつは自分より背が小さくてかつ間に自分より背が高いのはいない　なのでそいつと同じだけのところまで見れる
・stackに身長と計算結果を追加

※スタックに積んである身長が単調増加するようにしてある

↑矢印が、スタックの先頭をポップする動作を表している

例題
3250 -- Bad Hair Day

#include <cstdio>
#include <utility>
#include <stack>
#include <iostream>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

typedef long long i64;
int N;
i64 h[80001];
i64 calc() {
    stack<pair<i64, i64> > sta;
    i64 sum = 0;
    rep(i, N) {
        i64 k = i;
        while(!sta.empty() && sta.top().first < h[i]) {
            k = sta.top().second;
            sta.pop();
        }
        sum += i - k;
        sta.push(make_pair(h[i], k));
    }
    return sum;
}
int main() {
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &h[N - i - 1]);
    printf("%lld\n", calc());
    return 0;
}