BOJ 20846 수열과 쿼리 40¶

https://acmicpc.net/problem/20846

이게 무슨 쿼리야?¶

각각의 쿼리는 수열 B의 [[접미사 배열]]을 만들었을 때 K번째 원소가 무엇인지 묻는 쿼리로 생각할 수 있습니다.

수열 A의 접미사 배열을 만들고, 쿼리를 (d mod M)에 대한 오름차순으로 정렬합니다. 이제 d를 하나씩 올려 가는데, 그럴 때마다 수열 A의 모든 원소를 하나씩 올린다고 생각하지 말고, A에 있는 원소 중 M-d가 "새로운 최솟값"이 된다고 합시다. 이렇게 하면 원소가 바뀌는 횟수는 최대 N회입니다. 이제 관건은 접미사 배열을 어떻게 동적으로 관리하는지입니다.

자료구조¶

정해가 이것일지는 모르겠으나, 저는 [[접미사 트리]]로 풀었습니다.

접미사 트리는 여러 강력한 기능을 갖고 있는데, 그중 하나는 트리를 DFS 순회하되 사전순으로 작은 자식부터 차례대로 방문하면 (termination symbol은 -1이라고 합시다), 리프 노드를 방문한 순서가 곧 접미사 배열이 된다는 것입니다. 따라서 수열 A의 접미사 트리를 만들고, 오일러 투어 트릭을 써서 일자로 편 다음, 그걸 동적으로 관리함과 동시에 K번째 리프 노드를 찾을 수 있으면 됩니다.

이제 원소 M-d가 "새로운 최솟값"이 된다고 합시다. 그러면 모든 노드 p에 대해, label이 M-d로 시작하는 자식 v가 (존재하면) 현재 마지막 자식일 것이고, 이 v가 첫 번째 자식으로 옮겨집니다. 단, label이 termination symbol로 시작하는 자식이 있으면 대신 두 번째 자식으로 옮겨집니다. 오일러 투어 트릭을 생각해 보면 이는 부분배열을 잡아서 v의 서브트리의 크기 만큼 오른쪽으로 시프트하는 것이라고 생각할 수 있습니다.

따라서 다음을 지원하는 자료구조를 사용하면 됩니다.

접미사 트리의 노드가 주어졌을 때, 이것이 현재 오일러 투어에서 몇 번째에 위치하는지 찾기
부분배열을 오른쪽으로 시프트하기
현재 오일러 투어에서 K번째 리프 노드 찾기

자료구조 하나 더¶

[[스플레이 트리]]로 위 셋을 전부 구현할 수 있습니다.

1번 연산은 접미사 트리의 노드 v에 대응되는 스플레이 트리의 노드 x를 찾고, x를 스플레이한 다음 x의 왼쪽 서브트리의 크기를 구하면 됩니다.
2번 연산은 부분배열 뒤집기 연산 세 번으로 구현할 수 있습니다.
3번 연산은 스플레이 트리의 각 노드마다 "해당 (스플레이 트리) 노드의 서브트리에 있는 접미사 트리의 리프 노드 개수"를 저장해 두고, 루트에서부터 하나씩 내려가면 됩니다. 단, 그 전에 스플레이 트리가 균형이 잡혀 있음이 보장되어야 O(logN)이 됩니다. 만약 그게 보장이 안 된다면, 스플레이 트리를 만든 직후에 아무 노드나 잡아서 스플레이하는 걸 10,000번 정도 반복하면 됩니다.

루비5 티어 문제인 만큼 자세한 구현 디테일은 생략했습니다. 참고로 제 코드는 10799 바이트입니다.