Lưu ý: Giới hạn thời gian của bài này là 4 giây, gấp đôi giới hạn mặc định.

Farmer John có một cây nhị phân gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\) (\(1 \leq N < 2\cdot 10^5\) và \(N\) là số lẻ). Với \(i>1\), cha của đỉnh \(i\) là \(\lfloor i/2\rfloor\). Mỗi đỉnh có một giá trị nguyên ban đầu \(a_i\) và một chi phí \(c_i\) để đổi giá trị ban đầu thành bất kỳ giá trị nguyên nào khác (\(0\le a_i,c_i\le 10^9\)).

Federal Bovine Intermediary (FBI) đã giao cho ông nhiệm vụ tìm một giá trị trung vị xấp xỉ trong cây này, và ông đã nghĩ ra một thuật toán thông minh để làm vậy.

Ông bắt đầu tại đỉnh cuối cùng \(N\) và lần lượt đi ngược lại. Tại mỗi bước của thuật toán, nếu một đỉnh không phải là trung vị của chính nó và hai con của nó, ông hoán đổi giá trị của đỉnh hiện tại với giá trị của đỉnh con mà lẽ ra là trung vị. Khi thuật toán kết thúc, giá trị tại đỉnh \(1\) (gốc) là trung vị xấp xỉ.

FBI cũng đưa cho Farmer John danh sách \(Q\) (\(1 \leq Q \leq 2\cdot 10^5\)) truy vấn độc lập, mỗi truy vấn được xác định bởi một giá trị mục tiêu \(m\) (\(0\le m\le 10^9\)). Với mỗi truy vấn, trước tiên FJ sẽ thay đổi một số giá trị ban đầu của các đỉnh, rồi thực thi thuật toán xấp xỉ trung vị. Với mỗi truy vấn, hãy xác định tổng chi phí nhỏ nhất có thể để FJ khiến đầu ra của thuật toán bằng \(m\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(c_i\).

Dòng tiếp theo chứa \(Q\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một giá trị mục tiêu \(m\).

Dữ liệu ra

In \(Q\) dòng, mỗi dòng là tổng chi phí nhỏ nhất có thể ứng với giá trị mục tiêu \(m\) tương ứng.

Ví dụ

5
10 10000
30 1000
20 100
50 10
40 1
11
55
50
45
40
35
30
25
20
15
10
5

111
101
101
100
100
100
100
0
11
11
111

Phân nhóm

• Inputs 2-4: \(N,Q\le 50\).
• Inputs 5-7: \(N,Q\le 1000\).
• Inputs 8-16: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Gold — Median Heap

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1473

Tác giả đề: Suhas Nagar và Benjamin Qi