#16160 이진 트리와 수열

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

 

우선 각 깊이에서 특정한 순열들이 반복됨을 알 수 있다.

예를 들어 예제의 4번째 깊이에서는 (2), (3), (1)이, 3번째 에서는 (2, 3), (1, 2), (3, 1)이 반복된다.

따라서 한 주기에서 각 순열 조각이 몇 번 등장하였는지만 세주면 k를 넘는지는 쉽게 확인할 수 있다.

 

다만 길이가 2^(H - depth)인 조각들을 정직하게 비교하는 것은 너무 오래 걸린다.

여기서 사실 이들이 처음 주어진 수열에서 substr(i, (1 << d)), substr(j, (1 << d))이란 것에 착안할 수 있다.

이와 비슷한 작업은 Suffix array를 만드는 과정에서 본 적이 있다!

 

예를 들어 모든 i에 대해 substr(i, (1 << (d - 1)))를 정렬했을 때 i번째 substr의 순위를 inv[i]라고 하자.

이때 만약에 substr(i, (1 << (d - 1))) = substr(j, (1 << (d - 1)))이면 inv[i] = inv[j]라고 하자.

그렇다면 substr(i, (1 << d))의  순서를 얻을 때 무려 1 << d 길이의 수열을 비교하는 것이 아니라

pair(inv[i], inv[i + (1 << (d - 1))]), pair(inv[j], inv[j + (1 << (d - 1))])를 비교해주면 된다.

따라서 그냥 O(nlgn)으로 이들을 정렬해서 다음을 위한 inv 값을 얻을 수 있다.

inv의 정의에 의해서 inv값이 같다면 substr 또한 값이 같음을 알 수 있다.

따라서 한 주기를 돌면서 각 inv값이 몇 번 나오는지 세주면, 간단하게 특정 수열 조각이 몇 번 나오는지 알 수 있다.

 

어차피 한 깊이에서의 주기는 N을 넘지 못하기에 복잡도는 NlgN * H가 된다.

아마 radix sort 등을 활용한다면 N*H도 가능하겠지만, 시간 제한이 3초로 넉넉하기에 시간은 충분하다.