이진 탐색 트리(BST) (JUNGOL 3579)

https://jungol.co.kr/problem/3579?cursor=MTMsMSwy

---

아이디어

지금까지 들어간 수들을 정렬해봅시다. 그리고 새로운 수 x를 넣는다고 해봅시다. 그러면 x이상의 가장 작은 수와 x이하의 가장 큰 수가 있을것입니다. 그 두 수의 깊이의 최댓값 +1이 이 수 x의 깊이가 됩니다. 이를 std::set을 이용하여 구현해주면 됩니다.

---

소스코드

#include <iostream>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,x,sum=0;
    set <pair <ll,ll> > st;

    cin>>N;
    for (i=1;i<=N;i++)
    {
        cin>>x;

        auto iter=st.lower_bound({x,0});

        ll num=0;
        if (iter!=st.end()) num=max(num,(*iter).second+1);
        if (iter!=st.begin()) num=max(num,(*prev(iter)).second+1);

        sum+=num; st.insert({x,num});
        cout<<sum<<"\n";
    }
}