[PS 켠왕 #1] BOJ 10641 The J-th Number

PS에 적당한 시간을 할애하기 위해서, 트위치에서 어려운 문제를 푸는 방송을 시작했다. 방송을 할 때마다 Write-up을 써볼 생각이다.

 

처음으로 푼 문제는 JAG Spring Contest 2013 I번으로 출제된 The J-th Number이다.

켠왕을 걸 정도로 어려운 문제는 아니었던 것 같지만 11번 틀렸다(...)

 

BOJ

 

문제 요약

 

\(N\)개의 빈 배열이 있는데, 여기에 \(M\)개의 삽입 쿼리를 먼저 수행한 뒤 \(Q\)개의 구간 쿼리에 답해야 한다.

 

삽입 쿼리 : \(a\)번 이상 \(b\)번 이하의 배열에 원소 \(v\)를 삽입한다.

구간 쿼리 : \(s\)번 이상 \(e\)번 이하의 모든 배열에서 \(j\)번째로 작은 수를 출력한다. 이 수가 존재함은 보장된다.

 

---

스포방지선

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

풀이 1. Segment Tree + Parallel Binary Search

 

구간 쿼리 \([s,e,j]\)가 하나만 있다면 세그먼트 트리 + 이분 탐색으로 이 문제를 쉽게 해결할 수 있다.

"답이 \(v_{k}\)이하인가?"로 정의되는 결정 문제를 살펴보자.

삽입 쿼리들을 모두 정렬해놓고, \(v_{i} < v_{k}\)인 모든 삽입 쿼리 \([a,b,v]\) 를 보면서 매번 합 세그트리의 구간 \([a,b]\)에 1을 더하면, 업데이트가 끝난 세그트리에서 구간 \([s,e]\)의 합이 \(j\)이상이 되는지를 체크하면 결정 문제를 해결할 수 있다. 물론 세그트리에 리프 노드가 \(10^9\)개 필요해지지만, dynamic segment tree를 쓰거나 좌표 압축을 사용하면 된다. 디테일은 생략.

당연히 여기서 이분탐색을 뗄 수도 있지만, 풀이의 맥락을 해치기 때문에 설명하지는 않는다.

 

이 문제는 다행히 쿼리가 많아져도 Parallel Binary Search가 먹히는 문제다.

\(M\)개의 \(v\)들을 압축해서 생각하자. \(Q\)개의 구간 쿼리에 대해 이분탐색 범위 \([l_{i}, h_{i}]\)를 관리한다.

초기에는 \(l_{i} = 0, h_{i} = M-1\)이다. PBS의 한 스텝은 다음과 같다.

 

\(l_{i} = h_{i}\)인 쿼리는 이미 이분탐색이 종료된 쿼리이다. 이 경우 \(l_{i}\) (정확히는 \(v[l_{i}]\))가 답이 된다.

\(l_{i} < h_{i}\)인 쿼리에 대해, \(m_{i} = (l_{i} + h_{i})/2\)를 계산하고, pair \((m_{i}, i)\)를 정렬한 배열 \(A\)를 얻는다.

이제 쿼리가 1개일 때 한 것처럼 세그먼트 트리 업데이트 - 결정문제 체크를 반복해주면 된다. PBS는 이렇게 쿼리 여러 개를 한 번의 sweeping으로 해결할 수 있을 때 매우 유용하다.

 

시간복잡도는 \(\mathcal{O}\left((M+Q)\lg Q \lg (M+Q)\right)\)이고, 공간복잡도는 \(\mathcal{O}\left(M+Q\right)\)이다.

Dynamic Segment Tree를 쓰면 공간복잡도가 \(\mathcal{O}\left((M+Q)\lg N\right)\)이 되고, 시간도 2배 정도가 되어서 잘 안 나온다. 편하게 압축하자...

 

---

풀이 2. Persistent Segment Tree

이건 구현해보지는 않았고, rkm0959가 열심히 짠 풀이다. 약간 원래의 풀이에서 time-space tradeoff를 했다는 느낌이 진하게 난다. 대강의 설명만 적어두자.

 

PBS 과정을 생각해보면, 매번 세그먼트 트리에 업데이트하는 과정을 새로 시작할 필요 없이 업데이트 로그를 전부 저장해두면 된다는 것을 알 수 있다. 그럼 그냥 PST로 그 짓을 구현하면 각각의 구간 쿼리가 들어올 때마다 1회의 이분탐색으로 답을 할 수 있다! 좌표 압축 때문에 입력을 미리 받고 시작해야 하긴 하지만...

 

물론 AC까지는 몇 가지 병목이 있다.

- PST의 \(M\)개의 루트 노드에서 이분탐색을 할 수도 있지만, 안 그래도 PST 상수가 큰데 로그제곱 복잡도는 위험하다. 세그먼트 트리에서 \(k\)번째 수를 찾는 트릭을 응용하면, 이분탐색 없이 세그먼트 트리 탐색 한 번만으로 답을 낼 수 있다. 그래서 시간복잡도 \(\mathcal{O}\left((M+Q)\lg (M+Q)\right)\)가 완성되고, 공간복잡도도 똑같이  \(\mathcal{O}\left((M+Q)\lg (M+Q)\right)\)가 된다.

 

- 그냥 세그먼트 트리에서 range update - range query는 lazy propagation으로 쉽게쉽게 할 수 있지만, PST에서 lazy는 된...다고 들었는데 짜본 적도 없고 많이 귀찮다. BOJ 17353에 쓰이는 트릭처럼, 구간 업데이트를 점 업데이트 2개로 바꾸면 편하게 구현할 수 있다고 한다.

 

---

코드

실제로 켠왕에 사용한 소스코드이다. 풀이 1로 구현되었다.