3015번: PATRIK

https://www.acmicpc.net/problem/3015

$O(n)$

입력으로 A[1..n]이 차례대로 주어진다.
monotonous stack를 이용해 A[1..i-1]의 단조 감소 수열 a[1..i-1]을 구해놓았다고 하자.
(이 수열은 i<j이고 A[i]<A[j]일 때, A[i]를 제거한 수열이다.)
1..i-1번째 사람 중 i번째 사람과 서로 볼 수 있는 사람은 a[1..i-1]에서 A[i]보다 작거나 같은 사람과 A[i]보다 큰 사람 중 키가 가장 작은 사람이다.

#include<cstdio>
int n, a[500001], c[500001], m, x;
long long r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        while (m > 0 && a[m] < x) r += c[m--];
        if (a[m] == x) r += c[m]++;
        else a[++m] = x, c[m] = 1;
        r += m > 1;
    }
    printf("%lld", r);
    return 0;
}