LIS(Longest Increasing Subsequence) 문제는 너무나도 유명하다. 이미 알고 있는 사람은 밑의 문제로 넘어가도 좋다.

어떤 수열의 부분 수열이라 함은, 원래 수열에서 몇 개의 원소를 뽑아 순서를 유지한 채 나열한 수열을 뜻한다.

예를 들어서 수열 [7 2 5 3 4 9 1] 에서

[7 5 3 4]나 [2 9]는 부분 수열이지만,

[1 2 3 4]는 원소의 순서가 바뀌었기 떄문에 부분 수열이 아니다.

증가 수열이라 함은, 말 그대로 모든 수열의 원소가 증가하는 순서대로 나열되어 있음을 뜻한다.

부분 증가 수열은 주어진 원래 수열의 부분 수열이면서 증가 수열이기도 한 수열을 뜻한다.

최장 부분 증가 수열은 주어진 수열에서 만들 수 있는 부분 증가 수열 중에서 가장 긴 수열을 뜻한다.

우리의 목적은 주어진 수열로 찾을 수 있는 최장 부분 증가수열의 길이, 즉 LIS의 길이를 찾는 것이다.

문제

크기 N의 수열이 주어졌을 때, 그 수열의 LIS의 길이, 즉 최장 부분 증가수열의 길이를 찾아 출력하라.

전깃줄(중) 문제를 푼 사람이라면 이진 탐색을 통한 O(N log N)해법은 이미 알고 있을 것이다.

이번에는 Segment Tree를 사용하여 풀어본다.

어떤 해법을 써야만 100점을 주게 한다던가 하는 채점장치는 따로 없지만,

여러분 본인들의 훈련을 위하여 Segment Tree를 사용하여 이 문제를 풀어보는 연습을 하도록 한다.

첫 줄에 수열의 길이 N(1≤N≤500,000)이 주어진다.

둘째 줄에 공백을 사이에 두고 N개의 수열의 원소들 a_i(1≤​a_i≤​10⁹)가 주어진다.

첫 줄에 LIS의 길이를 출력한다.

도무지 감이 안잡힌다~ 하는 학생의 경우,

우선 전깃줄(초) 문제처럼 O(n²), 즉 2중 포문으로 먼저 풀어보도록 하자.

O(n²)으로 풀면 시간초과로 50점이 나온다.

그 후에 점화식을 보고 구간 트리를 어떻게 사용하면 좋을지 생각해 보자.