BOJ 11932 - 트리와 K번째 수

열심히 풀고 기여를 하러 갔는데, 다들 내 풀이와 방향성이 다른 것 같았다. 정해가 시간 복잡도 면에서도, 난이도 면에서도 조금 더 낫지만 내 풀이도 의미가 있다고 생각해 적어보려 한다.

 

해당 풀이는 7469 - K번째 수를 PST로 푸는 방법을 트리로 확장시켜 적용한다.

간단하게 요약을 하자면, 인덱스 순으로 세그트리를 \(N\)개 만든 후 \(R\)번째 세그트리에서 \(L-1\)번째 세그트리를 뺀 값으로 세그 이분탐색을 해서 K번째 수를 찾는다. (이 과정에서 배열의 각 수에 대해 좌표압축을 해 주어야 한다.)

세그 이분탐색이란 왼쪽 자식의 합과 K를 비교해 K가 크면 오른쪽, 그렇지 않으면 왼쪽으로 가는 작업을 반복하는 것을 말하며, 세그트리를 여러 개 만드는 것은 PST를 통해 수행할 수 있다.

 

그렇다면, 트리를 적당히 직선으로 핀 후 경로에 해당하는 구간을 \(logN\)개 정도로 나타낼 수 있다면 전체 문제를 \(O(Qlog^2N)\)정도에 해결할 수 있을 것이라 유추할 수 있다.

트리의 경로를 구간으로 나타내는 것은 HLD를 진행해주면 됨이 널리 알려져 있으니, 이를 사용하자.

각 정점에 DFS ordering을 해준 후, 이 번호를 토대로 K번째 수와 같은 PST를 만든다. HLD를 사용하면 트리의 임의의 경로에 대해 구간을 \(logN\)개로 쪼갤 수 있으니, 더해야 하는 세그트리의 번호와 빼야 하는 세그트리의 번호를 잘 저장해준 후 세그 이분탐색을 해주면 문제를 해결할 수 있다.

 

정해는 PST를 DFS order로 만드는 것이 아니라 부모의 세그트리에서 업데이트를 해준 후 LCA를 누적합처럼 빼 주는 것이며, 그 외에도 PBS와 HLD를 사용한 풀이 등이 있는 것으로 보인다.

추가로, 13517 - 트리와 쿼리 8 또한 동일한 문제이기 때문에 같은 방법으로 해결할 수 있다.