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의 서브트리의 크기 만큼 오른쪽으로 시프트하는 것이라고 생각할 수 있습니다.

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

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

자료구조 하나 더

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

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

참고로 제 코드는 10799 바이트입니다.