K-th Longest Increasing Subsequence (Hard)

Spoiler!

 

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

 

---

 

우리는 이전 글에서 다음과 같은 문제를 해결해 보았다.

 

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

 

이제 임의로 추가했던 세 번째 조건을 삭제하고 풀어보도록 하자. 만약 $A_{i}=A_{j}$인 경우가 존재한다면 풀이에 어떤 영향을 줄까? 가장 먼저, $LIS$의 첫 원소를 고정하고 부분 문제를 만들었을 때 각 $A_{i}$에서 시작하는 $LIS$의 개수가 $C[i]$와 같지 않을 수 있다. 

 

다음과 같은 예제 입력을 생각해보자.

 

6 3
1 3 1 3 5 5

 

• $L[i]=3$을 만족하는 $A_{i}$는 1로 유일하므로 $A_{2},A_{3},...,A_{6}$의 6번째 $LIS$를 구해야 한다.
• $L[i]=2$를 만족하는 $i$에 대해 $C[i]$를 살펴보면 $C[2]=2, C[4]=2$이다.
• 합이 6을 넘지 못하므로 조건을 만족하는 수열이 존재하지 않는다.
• WA

 

무언가 잘못되었음을 알 수 있다. 이러한 문제가 발생하는 이유는 앞서 $C[i]$를 '첫 항이 $C[i]$보다 큰 $A_{i+1}, A_{i+2}, ..., A_{N}$ 의 $LIS$ 개수'로 정의했기 때문인데, 이는 다음과 같은 가정으로 이어졌다.

 

고정된 첫 항 $A_{i}$를 포함하는 $LIS$의 개수는 $\sum_{L[i]=L[x]+1} C[x] \: (i<x)$ 와 일치한다.

 

따라서 $A_{i}=A_{j}$인 두 쌍이 존재할 경우, 첫 항이 어떤 수인지 고정하는 방법은 위 가정을 더이상 만족하지 않는다. 그러므로 $LIS$의 첫 항을 고정하고 부분 문제로 만드는 아이디어를 적용하기 위해서는 $C[i]$가 위 가정을 만족하도록 수정되어야 함을 알 수 있다.

 

$LIS$의 첫 항 $k$가 여러 $A_{i}$로부터 올 수 있기 때문에 첫 항이 $k$로 고정된 $LIS$의 개수에 $C[x]$가 기여하는 횟수는 $A_{i}=k,i<x$를 만족하는 $i$의 개수와 같고,

 $D[x]=\sum_{A_{i}=A_{j}} C[x] \: (j<x)$ 와 같이 항을 수정함으로써 식을 다시 정의할 수 있다.

 

첫 항이 $k$인 $LIS$의 개수는 $\sum_{L[i]=L[x]+1} D[x] \: (i<x)$ 와 일치한다.
(단, $i$는 $A_{i}=k,L[i]=(LIS의\:길이)$를 만족하는 $i$ 중 최소)

 

이제 $D[i]$를 빠르게 구할 수만 있다면 부분문제를 풀 수 있고, 수열 $A$의 구간 $[i,x-1]$에서 $k$의 개수를 $cal(i,x,k)$로 정의할 경우 $D[x]=C[x]\times cal(i,x,k)$로 표현된다.

 

이는 $A_{i}=k$를 만족하는 $i$마다 $[i,N]$에 $v$를 더하는 구간 갱신과 어떤 점 $x$의 값을 구하는 쿼리를 수행하는 세그먼트 트리를 이용해 쿼리당 $O(lgN)$에 처리할 수 있고, 각 숫자마다 요구되는 update와 query가 최대 한 번이므로 전체 시간복잡도 $O(NlgN)$만에 문제를 해결하게 된다.

 

---

 

TMI

• 이 문제는 펜윅 트리로도 해결할 수 있다. 
• $L[i]$와 $C[i]$, $D[i]$를 구하는 연산의 공통점을 이용하면 문제를 푸는 데 펜윅 트리 하나면 충분하다.