solved.ac CLASS 7 구간 트리 문제 정리

solved.ac

서론

이 글에서 제시된 문제 중 Fenwick Tree로 풀이할 수 있는 문제들은 Segment Tree로 풀이할 수도 있습니다.

일부 스포일러가 존재합니다.

 

1. BOJ 10999번 - 구간 합 구하기 2

RURQ Fenwick Tree

 

2. BOJ 16975번 - 수열과 쿼리 21

RUPQ Fenwick Tree

 

3. BOJ 16978번 - 수열과 쿼리 22

Fenwick Tree + offline query

 

4. BOJ 13537번 - 수열과 쿼리 1

Fenwick Tree + offline query or Merge Sort Tree

 

5. BOJ 13544번 - 수열과 쿼리 3

13537번을 online으로 강제한 버전이다.

 

6. BOJ 16404번 - 주식회사 승범이네

RUPQ Fenwick Tree + Euler Tour Technique

 

7. BOJ 18227번 - 성대나라의 물탱크

Fenwick Tree + Euler Tour Technique

 

8. BOJ 10277번 - JuQueen

Segment Tree with Lazy Propagation

좌표 압축을 하면 조금 빨라지지만 필수는 아니다.

 

9. BOJ 17353번 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

RURQ Fenwick Tree로 풀이할 수 있다.

1번 쿼리는 [l, r] 구간에 1을 더하고 인덱스 (r + 1)에 (l - r - 1)을 더하여 처리할 수 있다.

2번 쿼리는 [1, x] 구간의 합을 구하면 된다.

 

10. BOJ 14897번 - 서로 다른 수와 쿼리 1

여러 풀이가 존재한다.

 

풀이 1. Mo's algorithm

별다른 설명이 필요 없다.

 

풀이 2. RUPQ Fenwick Tree + offline query

query를 r이 작은 순으로 정렬하자.

그리고 x가 마지막으로 등장한 인덱스를 D[x]라고 하자.

인덱스 i에 대한 업데이트는 [D[A[i]] + 1, i] 구간에 대한 업데이트로 처리할 수 있다.

 

풀이 3. Merge Sort Tree

다음과 같은 배열 B를 구성하자.

B[i] = i < j && A[i] == A[j]를 만족하는 j의 최솟값

배열 B로 Merge Sort Tree를 구성하고 r보다 큰 값의 개수를 세주면 된다.

 

풀이 4. Persistent Segment Tree

필자는 PST를 모르므로 생략한다.

 

추가적으로 14898번은 14897번을 online으로 강제한 버전이며 풀이 3 또는 풀이 4로 풀이할 수 있다.

 

11. BOJ 2912번 - 백설공주와 난쟁이 (PATULJCI)

여러 풀이가 존재한다.

 

풀이 1. Mo's algorithm

놀랍게도 O(MC)가 돌아간다.

 

풀이 2. Segment Tree

이 풀이는 공식 솔루션을 참고하였다.

 

구간 내에 서로 다른 값이 존재하면 임의의 서로 다른 두 값을 제거하는 연산을 최대한 수행한다고 가정하자.

이때 dominating color가 존재한다면 항상 dominating color가 남게 된다.

그렇지 않다면 임의의 color가 남거나 아무런 color도 남지 않게 된다.

따라서 최종적으로 남은 color는 dominating color의 후보이다.

 

이제 Segment Tree의 각 노드가 최종적으로 남은 color와 개수를 관리하도록 하자.

구간 query를 수행하면 특정한 color를 얻을 수 있고 이 color가 dominating color인지 검증만 해주면 된다.

검증 작업은 전처리 후 이분 탐색으로 해결할 수 있다.

 

풀이 3. Randomization

특정 구간에 dominating color가 존재한다고 가정하자.

해당 구간 내의 임의의 color가 dominating color일 확률은 1/2 이상이다.

따라서 임의의 color를 선택하고 해당 color가 dominating color인지 검증하는 작업을 K번 반복하여 문제를 해결할 수 있다.

dominating color가 존재할 때 dominating color를 찾지 못할 확률은 1/2^K 미만이다.

검증 작업은 전처리 후 이분 탐색으로 해결할 수 있으며 K는 20~30 정도가 적절하다.

 

끝

끝