POPA
시간 제한1초메모리 제한512 MB
인덱스의 중위 순회가 0..N-1이 되고 부모의 가중치가 자식의 가중치를 나누는 이진 트리를, 숨겨진 부분 배열의 gcd 비교 질의를 Q번 이하로 써서 구성한다.
문제
“He’s an outlaw and he’s famous Andrii Popa the courageous.
Day and night he rides, He takes his tribute from the main road And everywhere in the country The thief catchers are running away as fast as they can”
- “Andrii Popa”, Phoenix
Ghiță는 양의 정수 가중치 N개로 이루어진 0-indexed 수열 S를 가지고 있다. 그는 카르파티아 산맥의 왕이므로, 노드의 인덱스가 0, 1, …, N - 1인 이진 트리를 다음과 같이 만들고자 한다.
- 트리를 중위 순회하면 인덱스가 증가하는 순서대로 노드를 방문한다. 이진 트리의 중위 순회는 루트의 왼쪽 자식을 루트로 하는 부분 트리의 중위 순회(자식이 존재하는 경우), 루트의 인덱스, 루트의 오른쪽 자식을 루트로 하는 부분 트리의 중위 순회 순으로 구성된다.
- 노드 x가 노드 y의 부모라면 Sx는 Sy를 나눈다.
이진 트리란 각 노드가 왼쪽 자식과 오른쪽 자식이라 불리는 최대 두 개의 자식을 가지는 트리 자료 구조이다.
안타깝게도 악명 높은 무법자 Andrii Popa가 수열 S를 훔쳐 가서 Ghiță는 더 이상 S에 직접 접근할 수 없다. 최신 기술(휴대폰)을 이용하면 S의 임의의 두 연속 부분 수열 [a, b]와 [c, d]에 대해 gcd[a, b]가 gcd[c, d]와 같은지 알아낼 수 있다. 여기서 gcd[x, y]는 Sx, Sx+1, Sx+2, …, Sy의 최대공약수이다. 하지만 이 기술은 매우 비싸서, Ghiță가 Q번을 초과하여 사용하면 큰 벌금을 내야 한다. 그가 원하는 트리를 만들 수 있도록 기술을 최대 Q번 사용하여 도와주자. 가능하다는 것이 보장된다. 어떤 유효한 답이든 허용된다.
힌트
앞의 예제에 대해 Ghiță가 원하는 종류의 트리의 예는 다음과 같다.
