K-th Longest Increasing Subsequence (Easy)

Spoiler!

 

이 포스팅은 BOJ 18838: 가장 긴 증가하는 부분 수열 k의 풀이를 설명하고 있습니다

 

---

 

N개의 수로 이루어진 수열 $A_{1}, A_{2}, ..., A_{N}$ 에서 특정 원소를 지워서 만든 수열 $A_{i_{1}}, A_{i_{2}}, ... , A_{i_{L}}$ 을 생각하자. 이렇게 만들어진 수열이 모든 $x<y$ 에 대해 $A_{i_{x}}<A_{i_{y}}$ 를 만족할 때 '증가한다'고 하고, 이러한 수열 중 길이 $L$이 최대인 것을 $LIS$(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열) 라고 부른다.

 

주어진 수열에 대해 $LIS$의 길이를 구하거나, 혹은 사전순으로 가장 앞서는(lexicographically minimal) $LIS$를 구하는 문제는 동적 계획법과 이분 탐색을 통해 $O(NlgN)$ 만에 해결할 수 있음이 잘 알려져 있다.

 

그렇다면 다음 문제는 얼마나 빠르게 해결할 수 있을까? 이 또한 $O(NlgN)$ 만에 풀 수 있을까?

 

길이가 $N$인 수열 $A_{1}, A_{2}, ..., A_{N}$ 의 모든 $LIS$를 사전 순으로 정렬했을 때, $K$번째 $LIS$를 출력하라.
$1<=N<=10^5, 1<=K<=10^{18}, 1<=A_{i}<=N$
수열 A에는 중복되는 수가 없다

 

이 문제를 풀기 위한 아이디어는 $LIS$의 길이를 구하기 위한 동적 계획법에서 얻을 수 있다. $A_{i}$에서 시작하는 $LIS$의 길이인 $L[i]$를 구하고자 할 때, 우리는 $A_{i+1}$부터 $A_{N}$까지의 수로 시작하는 부분 수열 중 $A_{i}$를 연결할 수 있는 가장 긴 수열을 찾고자 했고, $L[i]$에 대해 다음과 같은 식을 계산함으로써 $LIS$의 길이를 구할 수 있었다.

\[L[i] = \underset{i<x,\: A[i]<A[x]}{Max}L[x] +1\]

이때, 해당 식에 조건을 하나 추가하면 $A_{i}$에서 시작하는 $LIS$의 개수 $C[i]$를 구할 수 있게 되고

\[C[i] = \sum_{i<x,\: L[i]=L[x]+1} C[x]\]

$C[i]$를 이용해 주어진 수열의 $K$번째 $LIS\:$ $A_{k_{1}}, A_{k_{2}}, ... , A_{k_{X}}$ 에서 첫 번째 수의 인덱스 $k_{1}$을 다음과 같이 찾을 수 있다.

 

1. $L[i]=X$ 을 만족하는 모든 $i$를 오름차순으로 정렬한다.
2. 정렬된 $i$를 순서대로 보며 $C[i]>=K$ 를 만족할 때까지 $K$에서 $C[i]$를 빼준다.
3. 조건을 만족하는 모든 $i$에 대해 2.를 시행하고도 $K$가 양수라면, 주어진 수열의 $K$번째 $LIS$는 존재하지 않는다. 
4. 그렇지 않다면, $C[i]>=K$ 를 만족하게 되는 $i$ 가 $k_{1}$ 이다.

$k_{1}=i$ 을 구했다면 '첫 번째 원소가 $A_{i}$보다 큰' $A_{i+1}, A_{i+2},..., A_{N}$ 의 $K$번째 $LIS$를 구하는 부분문제를 대신 해결함으로써 답을 얻을 수 있다. 현재는 동적 계획법으로 모든 $i$에 대한 $L[i]$와 $C[i]$를 $O(N^2)$ 만에 계산했지만, $O(NlgN)$에 구하는 방법이 존재한다.

 

각 항의 정보를 빠르게 계산하기 위해 원래 식으로 돌아가보자.

\[L[i] = \underset{i<x,\: A[i]<A[x]}{Max}L[x] +1\]

위 식은 구간 $[i+1,N]$에 대해 $L[i]$의 최솟값을 구할 수 있는 세그먼트 트리를 만듦으로써 $O(lgN)$에 계산할 수 있다. 이제 $C[i]$를 빠르게 구하는 일만 남았다.

 

각 세그먼트 트리의 노드에 '해당 구간에서 $L[i]$의 최댓값'을 저장하던 것을 그 최댓값을 만족하는 $LIS$의 개수까지 같이 저장하도록 바꾸어 보자.

\[Seg[i] = (l[i],c[i])\]

이제 세그먼트 트리의 update 연산을 다음과 같이 바꾸면 $L[i]$와 $C[i]$ 모두 $O(lgN)$만에 계산할 수 있다.

\[l[i] = max(l[2i],l[2i+1])\]

\[c[i] =\left\{\begin{matrix} c[2i] \qquad\qquad\qquad l[2i]>l[2i+1] \\ c[2i+1] \qquad\qquad\ l[2i]<l[2i+1] \\ c[2i]+c[2i+1] \quad l[2i]=l[2i+1] \end{matrix}\right.\]

따라서 점 갱신 구간 쿼리를 수행하는 세그먼트 트리 하나로 모든 항의 정보를 빠르게 계산할 수 있고, 주어진 수열의 $K$번째 $LIS$를 구하는 문제를 $O(NlgN)$에 해결할 수 있다.