210. 가장 긴 증가하는 부분 수열 5

백준

1. 이분 탐색

참고1, 참고2

import sys
input = sys.stdin.readline

#오름차순으로 정렬된 배열에서 처음으로 특정 값 이상이 나오는 인덱스를 반환
def lower_bound(start, end, num):
  while start < end:
    mid = (start + end) // 2
    if tmp[mid] < num:
      start = mid + 1
    else:
      end = mid
  return end

n = int(input())
array = list(map(int, input().split()))

tmp = []
index = [[0,0] for _ in range(n)]

for i in range(len(array)):
  num = array[i]
  index[i][1] = num #현재 수 저장

  if len(tmp) == 0:
    tmp.append(num)
    continue
  if tmp[-1] < num:#tmp의 마지막 보다 크면
    index[i][0] = len(tmp) #tmp의 마지막 인덱스를 가지면 된다.
    tmp.append(num)
  else: #중간에 들어가야 한다면 이진 탐색
    idx = lower_bound(0, len(tmp)-1, num)
    index[i][0] = idx #tmp에서의 인덱스를 앞에 저장
    tmp[idx] = num

answer = []
idx = len(tmp) - 1
for i in range(len(index) - 1, -1, -1): #뒤에서 부터 찍기
  if idx == -1:
    break
  
  if idx == index[i][0]:
    answer.append(index[i][1])
    idx -= 1

print(len(tmp))
print(*answer[::-1])

#print(tmp)  # [(0, 10), (1, 20), (0, 10), (2, 30), (1, 20), (3, 50)]
#print(index)

import sys
from bisect import bisect_left
input = sys.stdin.readline

n=int(input())
a=list(map(int,input().split()))

q=[]
temp=[] # [(0, 10), (1, 20), (0, 10), (2, 30), (1, 20), (3, 50)]
for x in a:
    if not q or x > q[-1]:
        q.append(x)
        temp.append((len(q)-1, x))
    else:
        q[bisect_left(q, x)]=x
        temp.append((bisect_left(q, x), x))

ans=[]
last_idx=len(q) - 1
for i in range(len(temp)-1, -1, -1):
    if temp[i][0] == last_idx:
        ans.append(temp[i][1])
        last_idx-=1
print(len(ans))
print(*reversed(ans))

C++

#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define PIV (1<<20) 
#define INF 1000000005
using namespace std;
int tree[PIV * 2];
void update(int n, int v)
{
    tree[n += PIV] = v;
    while (n >>= 1)
        tree[n] = max(tree[n], v);
}
int query(int n)
{
    int l = PIV, r = n + PIV;
    int ret = 0;
    while (l <= r)
    {
        if (l & 1) ret = max(ret, tree[l++]);
        if (!(r & 1)) ret = max(ret, tree[r--]);
        l >>= 1, r >>= 1;
    }
    return ret;
}
int N, b[PIV], p[PIV], r[PIV];
struct st {
    int n, th;
};
bool operator<(st a, st b)
{
    if (a.n == b.n)
        return a.th > b.th;
    return a.n < b.n;
}
st a[PIV];
int main()
{

    scanf("%d", &N);
    for (int i = 0, n; i < N; i++)
        scanf("%d", &n), a[i] = { n, i }, p[i] = n;
    sort(a, a + N);
    int ans = 0, retval;
    for (int i = 0; i < N; i++)
    {
        int ret = query(a[i].th - 1);
        retval = ret + 1;
        update(a[i].th, retval);
        b[a[i].th] = retval;
        ans = max(ans, retval);
    }
    printf("%d\n", ans);

    int cnt = ans, ret = INF;
    for (int i = N - 1; i >= 0; i--)
        if (b[i] == cnt && p[i] < ret)
            r[--cnt] = p[i], ret = p[i];
    for (int i = 0; i < ans; i++)
        printf("%d ", r[i]);
    printf("\n");

}