Farmer John은 1 \le N < 2\cdot10^5개의 노드를 가진 이진 트리를 가지고 있다. 노드는 1부터 N까지 번호가 매겨져 있으며, N은 항상 홀수이다.

모든 i > 1에 대해, 노드 i의 부모 노드는 \lfloor i/2 \rfloor 이다. 각 노드는 초기 정수 값 a_i 와, 이 초기 값을 다른 정수 값으로 변경하는 데 드는 비용 c_i 를 가진다. (0 \le a_i, c_i \le 10^9)

Federal Bovine Intermediary (FBI)는 이 트리에서 근사 중앙값(approximate median) 을 찾는 작업을 FJ에게 맡겼다. 이를 위해 FJ는 다음과 같은 알고리즘을 고안했다.

FBI는 FJ에게 1 \le Q \le 2\cdot10^5 개의 독립적인 질의를 제공했다. 각 질의는 목표 값 m (0 \le m \le 10^9) 로 구성된다.

각 질의에 대해, FJ는 일부 노드의 초기 값을 변경한 후 근사 중앙값 알고리즘 을 실행한다.
이때, 알고리즘 실행 후 루트 노드의 값이 m 이 되도록 하는 최소 비용을 구하라.

중앙값 힙 timer 4s memory 1024MB

중앙값 힙 4s 1024MB