ARC098 E. Range Minimum Queries

문제 링크

길이 \(N\)의 수열에 대해서 다음의 쿼리를 \(Q\)회 수행한다 : 

- 길이 \(K\)인 연속한 subsequence를 잡아서 그 중 최솟값을 제거한다.

이 때, 제거된 \(Q\)개 수들의 (최댓값) - (최솟값)을 최소화하자.

---

Spoiler Alert!

---

tmi 함량이 높은 풀이입니다.

\(O(N^2 \lg N)\)으로 풀 수 있고, 에디토리얼에 의하면 \(N \le 10^{5}\)일 때도 가능하다고 한다.

\(N \lg N\)이나 \(N \lg^{2} N\)이겠지만 아직은 모르겠다...

맨 처음엔 대체 어떻게 풀지 싶어서 별 뻘짓을 다했다. 답을 이분탐색하려고 했는데 안되고, 분할정복 같은 걸 끼얹으려고 해도 안되더라.

그러다 문득 답이 결국 \(a\)의 두 원소의 차이라는 지극히 당연한 사실이 떠올랐고, \(O(N^2)\)개의 쌍에 대해서 validity를 판정하는 방법을 써보려고 했지만 잘 안 됐다. 조금 더 관찰해야 했다.

\(a\)를 오름차순으로 정렬한 수열을 \(b_1, b_2, \ldots b_n\)이라고 하자. 가장 naive한 시행으로, 현재 배열에 남아있는 최솟값이 포함되도록 Q번 쿼리를 날려주면 답은 \(b_{Q} - b_{1}\)이 된다. 그게 아니더라도 답은 \(b_{i+Q-1} - b_{i}\)꼴일 것 같았다.

오호라, 그럼 \(b_{i+Q-1} - b_{i}\)꼴이 답이 되려면? 쿼리에서 \(b_{i}\)미만의 수가 걸려들지 않아야 할 거고, 그럼 \(b_{i}\)미만의 수들을 기준으로 배열을 잘라주면 될 것 같다.

풀이가 완성되었다.

1. \(a\)를 좌표압축한다. 이 수열을 \(c_1 < c_2 <  \ldots < c_s\)라고 하자. O(NlgN).

2. pair 형태로 배열의 구간을 관리한다. 이 때 구간의 삽입 / 삭제가 빠르게 가능한 자료구조 (unordered_set)에 [1,n]을 넣는다.

3. i = 1 .. s까지. O(N).

3-1. 자료구조 내의 구간을 순회하면서, 가장 작은 (구간 길이) - K + 1개의 원소를 하나의 배열에 merge한다. O(NlgN).

3-2. 그 배열을 정렬한 것을 \(d\)라고 하면, 답의 후보는 \(d_{q} - d_{1}\)이 된다. (why?) O(NlgN).

3-3. 다시 구간을 순회하면서, \(c_{i}\)를 포함하고 있는 구간을 쪼개 새로운 구간을 만들어 넣는다. O(NlgN). 

4. 3에서 얻은 답의 후보 중 최솟값이 답이 된다.

전체 시간복잡도는 \(O(N^2\lg N)\)이다. 여기에 이분탐색을 잘 넣으면 \(O(Nlg^{2} N)\)도 될 것 같은데... 잘 모르겠다.