2957번: BST

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

$O(n\lg n)$

a[0...n-1]에 입력받은 순서대로 정수가 저장되어 있다고 하자.
a[i]는 a[0...i-1]를 가지고 만든 이진 탐색 트리에 추가하게 된다.
a[0...i-1] 중 a[i]보다 작은 최댓값, 큰 최솟값을 가진 노드를 각각 p, q라고 놓자.
만약 그러한 노드가 없다면 해당 p 혹은 q는 더미 노드로써 레벨이 -1이라고 생각하자.

다음 두 가지 경우가 가능하다.
i) p의 레벨 < q의 레벨
q의 왼편에 x를 추가하게 됨
ii) p의 레벨 > q의 레벨
p의 오른편에 x를 추가하게 됨

따라서 a[i]의 레벨은 max(p의 레벨, q의 레벨) + 1 이다.
map을 통해 (key = a[i], value = a[i]의 레벨)들을 관리하면 매 입력마다 이진 검색을 적절히 활용하여 위 과정을 수행할 수 있다.

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int n, x, t;
long long s;
map<int, int> mp = { { 0,-1 },{ 300001,-1 } };
int main() {
    for (scanf("%d", &n); n--;) {
        scanf("%d", &x);
        auto it = mp.upper_bound(x);
        t = it--->second;
        s += mp[x] = max(it->second, t) + 1;
        printf("%lld\n", s);
    }
    return 0;
}

$O(n)$

입력을 모두 받아 트리를 완성하고 반대로 노드를 하나씩 삭제한다.
이렇게 하면 map을 사용하지 않고 간단한 합집합 연산으로 각 시점의 (위에서 언급한)p, q를 구할 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 3e5;
int n, l[MXN + 2], r[MXN + 2], a[MXN + 1], p[MXN + 1], q[MXN + 1], lev[MXN + 2];
long long res;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        l[i] = i - 1;
        r[i] = i + 1;
    }
    for (int i = n; i; i--) {
        p[a[i]] = l[a[i]];
        q[a[i]] = r[a[i]];
        r[l[a[i]]] = r[a[i]];
        l[r[a[i]]] = l[a[i]];
    }
    lev[0] = lev[n + 1] = -1;
    for (int i = 1; i <= n; i++) {
        res += lev[a[i]] = max(lev[l[a[i]]], lev[r[a[i]]]) + 1;
        printf("%lld\n", res);
    }
    return 0;
}