14577번: 일기 예보

14577번: 일기 예보 - 구간트리 (세그먼트 트리)

kks227님 블로그의 오프라인 쿼리를 읽고 인상 깊어 작성하게 되었다.

이 문제에서는 4개의 쿼리가 있다.

1. 하나의 값에 X를 더한다.

2. 하나의 값에 Y를 뺀다.

3. 값이 L ~ R 사이인 원소의 개수를 구한다.

4. K번째로 큰 값을 구한다.

이러한 쿼리들을 10^5개를 처리해주면 되는 문제이다.

1번과 2번은 구간트리에서 많이 접해본 적이 있다.

어떤 idx에 대하여 X를 더하는, Y를 더하는 과정은 O(lgN)에 구할 수 있다.

3번 쿼리는 값이 L ~ R 사이인 원소들의 개수를 구하는 쿼리이다.

이 쿼리를 어떻게 처리해야할까?

나라들의 현재 값이 들어있는 배열을 A라 할 때 A = {1, 2, 10, 2, 4} 가 된다고 하자.

구간트리에 이 값이 들어있다고 하면

값이 2 ~ 4 사이인 원소들의 개수를 구하는 것은 어려운 일이다.

그러나 만약에 값들의 개수가 들어있는 배열 B가 있다면 어떨까?

위와 같은 배열이 B = {0, 1, 2, 0, 1, 0, 0, 0, 0, 0, 1} 이 되어

2 ~ 4사이인 원소의 개수는 구간 합을 이용하여 3개!라고 답을 할 수 있게 된다.

과연 이 방법으로 풀 수 있을까?

문제를 다시 한번 읽어보면 값들이 10^9은 넘어가는 것을 확인 할 수 있다.

10^9짜리의 배열을 만들 수는 없기에 힘들다고 판단할 수 있다.

그러나 이 때 나라들이 최대 10^5개, 쿼리들이 10^5개 이기에

매 쿼리에서 최대 1번만 바뀌게 되므로 값의 종류가 2 * 10^5개가 넘지 않는다는 것을 확인 할 수 있다.

이렇기에 오프라인 쿼리를 사용하여 쿼리를 입력 받으면서

나올 수 있는 값들을 모두 저장 해놓은 뒤 중복을 제외하고 정렬된 이 값들(C)을 사용한다.

이제 구간트리에서는 어떤 노드가 i ~ j까지의 구간합을 저장한다 할 때

값이 C[i] ~ C[j] 사이인 원소들의 개수가 들어있게 된다.

이제 해야할 일을 정리하기 전에 먼저

편의상 D[val] = 배열 C에서 val가 삽입 되었을 때 정렬을 깨뜨리지 않는 제일 작은 인덱스라고 정의하자.

이 값은 lower_bound를 이용해서 O(lgN)만에 구할 수 있다.

그러면 이제 매번 1, 2번 쿼리를 실행할 때마다

구간트리에서 D[이전 값]을 1 감소 시키고, D[바뀐 값]을 1 증가시킨다.

이 과정을 반복하다가 3번 쿼리를 만나면 D[L], D[R+1]의 구간을 더해주면 될 것이다.

이제 4번 쿼리만 남았다.

4번 쿼리는 K번째로 큰 값을 구하는 문제로

DP에서 했던 동적계획법 테크닉 중 하나인 k번째 답 찾기와 같은 원리를 이용하여

구간트리 내부에서 재귀적으로 구할 수도 있고

mid = (lo + hi)/2라고 할 때 [0 ~ mid]의 구간합을 이용하여

이분탐색으로도 찾을 수 있다.

이렇게 4개의 쿼리를 문제의 조건을 잘 이용하여 구간 합으로 구할 수 있는 방법으로 변환한 뒤 풀어주면 되는 문제이다.