14003 가장 긴 증가하는 부분 수열 5

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

LIS 배열을 구할 때 길이는 구할 수 있지만 실제 LIS의 순서를 보장하지는 않는다. 하지만 마지막 값이 정답의 마지막값임은 보장한다. 이 정보를 p 배열에 따로 담은 후 LIS 배열을 구한 후에 마지막 값의 인덱스를 이용해서 역추적하면 실제 LIS를 구할 수 있다.

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
 
int n,a[1000000],p[1000000];
vector<pii> l;
 
bool cmp(const pii &a,const pii &b)
{
    return a.second<b.second;
}
 
int main()
{
    scanf("%d",&n);
    l.push_back({-1,-1e9-1});
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if(l.back().second<a[i])
        {
            p[i]=l.back().first;
            l.push_back({i,a[i]});
        }
        else
        {
            auto low=lower_bound(l.begin(),l.end(),pii(0,a[i]),cmp);
            low->first=i;
            low->second=a[i];
            int idx=low-l.begin()-1;
            p[i]=l[idx].first;
        }
    }
    int len=l.size()-1,ptr=l.back().first;
    stack<int> st;
    for(int i=0;i<len;i++)
    {
        st.push(a[ptr]);
        ptr=p[ptr];
    }
    printf("%d\n",len);
    while(!st.empty())
    {
        printf("%d ",st.top());
        st.pop();
    }
    return 0;
}