백준) 15957 음악 추천 (퇴고전)

https://www.acmicpc.net/problem/15957

1. 트리

트리의 루트에 쿼리가 가해지면 자식들의 점수가 모두 더해진다.

-> 트리를 dfs 돌면서 번호를 매기면, 루트 노드 부터 자식들이 연속해서 들어있는 배열을 만들 수 있다. = 트리 순회 배열이라고 한단다.

2. 쿼리

트리 순회 배열에 쿼리가 가해진다.

이제 쿼리는 배열의 일부 구간을 증가시키는 쿼리가 된다.

-> 일부 구간을 빠르게 증가시키는 방법이 필요하다.

-> 증가시켰으면 값이 얼마인지도 빠르게 알아낼 방법이 필요하다. = 펜윅트리의 ( range update & point query ) 모드를 사용하자.

3. 펜윅 트리

이 자료구조는 다음 두 기능을 로그시간에 제공하는 자료구조다.

1) update(p, v) : p번째 원소를 v만큼 증가시킨다.

2) query(p) : 첫번째 원소부터 p번째 원소까지의 합을 알려준다.

즉 point update & range query를 로그시간에 수행한다.

이를 조금만 응용하면 range update & point query 모드로 바꿀 수 있다.

원래 배열을 a라고 하고, 배열 b[x] = a[x] - a[x - 1] 이라고 정의해보자.

그러면 이제 a의 입장에서, a[x]는 b[x] + b[x - 1] + ... 즉 누적합이 된다.

이제 두 기능을 b에 대고 수행한다고 생각해보자.

1) update(p, v)

-> 예를 들어 update(3, v)라면, a[1]과 a[2]는 가만히 있고, a[3]부터 v씩 늘어난 것이다. 왜냐하면 b의 정의 때문에.

따라서 [from, to] 구간을 v만큼 증가시키고 싶다면, update(from, v) 와 update(to + 1, v) 두 번으로 배열 a를 다 조질수 있다.

2) query(p)

-> b[1] + b[2] + ... + b[p] = a[p] 이니까, a의 p번째 원소 값을 구하는 쿼리로 변경되었다.

이처럼 펜윅트리는

1) point update & range query

2) range update & point query

3) range update & range query

총 3가지 모드를 제공한다. 3번째 모드는 차후에 설명하는 것으로.. ㅎㅎ

이제 트리에 가해지는 쿼리를, 펜윅트리에서 로그시간에 수행할 수 있게 되었다.

하지만

1) 모든 쿼리를 수행해보면서 매번 모든 가수가 평균 점수를 넘는지 확인

2) 모든 가수마다 쿼릐를 수행해보면서 언제 평균 점수를 넘는지 확인

어떤 방법으로도 N * K * log(N)으로 시간이 오바된다.

4. 시간 줄이기

포인트는 가수들의 평균점수는 쿼리들이 수행되는 동안 절대 내려가지 않는다는 점이다.

따라서 단조증가하고, 이는 이분 탐색을 떠올리게 해준다.

하지만 가수마다 이분 탐색으로 조지는 것 보다, 모든 가수들의 구간을 줄여나가는 방법이 있단다. -> 병렬 이분 탐색

이 알고리즘의 구조를 보면, 가수마다 구간이 있고 구간의 중앙값은 타겟이 된다.

이제 쿼리를 순차적으로 수행할 텐데, 현재 수행하는 쿼리가 타겟과 같다면 그 가수는 구간을 반으로 줄일 수 있다.

쿼리를 전부 수행하고 나서, 구간이 변화한 가수가 있다면, 다시 처음부터 쿼리를 수행하는 짓을 반복한다.

말로는 머가 개선된건지 모르겠지만, 나중에 코드로 보면 더 빠르겠구나 할 꺼다.