boj 12015: 가장 긴 증가하는 부분수열2

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

12015번: 가장 긴 증가하는 부분 수열 2

NlogN 으로 풀어야 한다.

증가수열 이므로 만약 새로운 인풋 x가 들어왔을때,   x1<x2<..<xk<x<a1<a2<..<am 형식의 기존 수열이 있었다면, 기존 x자리에 새 인풋인 똑같은 x를 집어넣는 작업을 해야한다. 왜냐면 upper_bound쓰면, x1<x2<..<xk<x<x<a2<..<am이 되어 모순이기 때문이다. 

 

#include<bits/stdc++.h>
using namespace std;

int main(){

    int n,x,c=0;
    cin>>n;
    vector<int> v;
    v.push_back(INT_MIN);
    for(int i=0;i<n;i++){
        cin>>x;
        if(x>v[v.size()-1]){
            v.push_back(x);
            c++;
        }else{
            int replace_idx = lower_bound(v.begin(),v.end(),x) - v.begin();
            v[replace_idx] = x;
        }
    }
    cout<<c<<'\n';

    return 0;
}