레이팅 미적용*참고: 이 문제의 시간 제한은 기본값의 두 배인 4초이다.*
농부 존은 노드가 \(N\)개인 이진 트리를 가지고 있다. 노드에는 \(1\)부터 \(N\)까지 번호가 매겨져 있다(\(1 \leq N < 2\cdot 10^5\)이고 \(N\)은 홀수). \(i>1\)에 대해 노드 \(i\)의 부모는 \(\lfloor i/2\rfloor\)이다. 각 노드는 초기 정수 값 \(a_i\)와, 초기 값을 다른 임의의 정수 값으로 바꾸는 데 드는 비용 \(c_i\)를 가진다(\(0\le a_i,c_i\le 10^9\)).
그는 연방 소 중개국(FBI)으로부터 이 트리 안에서 근사 중앙값을 찾는 임무를 받았고, 이를 위한 영리한 알고리즘을 고안했다.
그는 마지막 노드 \(N\)에서 시작하여 거꾸로 진행한다. 알고리즘의 매 단계에서, 어떤 노드가 자신과 두 자식 셋 중의 중앙값이 아니라면, 현재 노드의 값과 중앙값이 되는 자식의 값을 교환한다. 이 알고리즘이 끝났을 때 노드 \(1\)(루트)의 값이 중앙값 근사치이다.
FBI는 농부 존에게 각각 목표 값 \(m\)(\(0\le m\le 10^9\))으로 지정되는 \(Q\)개(\(1 \leq Q \leq 2\cdot 10^5\))의 독립적인 쿼리 목록도 주었다. 각 쿼리에서 농부 존은 먼저 일부 노드의 초기 값을 바꾼 뒤 중앙값 근사 알고리즘을 실행한다. 각 쿼리에 대해, 알고리즘의 출력이 \(m\)이 되도록 만들기 위해 농부 존이 지불해야 하는 총비용의 최솟값을 구하시오.
Problem credits: Suhas Nagar and Benjamin Qi
배점
- 입력 2-4: \(N,Q\le 50\)
- 입력 5-7: \(N,Q\le 1000\)
- 입력 8-16: 추가 제약이 없다
Problem credits: Suhas Nagar and Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 두 정수 \(a_i\)와 \(c_i\)가 주어진다.
다음 줄에 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 목표 값 \(m\)이 주어진다.
각 목표 값 \(m\)에 대한 총비용의 최솟값을 \(Q\)개의 줄에 출력한다.
5
10 10000
30 1000
20 100
50 10
40 1
11
55
50
45
40
35
30
25
20
15
10
5111
101
101
100
100
100
100
0
11
11
111To make the median approximation equal \(40\), FJ can change the value at node 3
to \(60\). This costs \(c_3=100\).
To make the median approximation equal \(45\), FJ can change the value at node 3
to \(60\) and the value at node 5 to \(45\). This costs \(c_3+c_5=100+1=101\).