Hướng dẫn giải của Clue Contest 05 - Cuộc họp khẩn NATO
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Nhận xét quan trọng: Tổng khoảng cách ~|x_i - X|~ nhỏ nhất khi ~X~ là median (trung vị) của tập hợp ~x_{l_k}..x_{r_k}~.
Ý tưởng:
Nén toạ độ:
- Do toạ độ có thể lớn, ta cần nén các giá trị ~x_i~ để dễ xử lý với segment tree.
Xây dựng Persistent Segment Tree (PST):
- Với mỗi ~i~, xây dựng version của PST chứa các phần tử ~x_1~ đến ~x_i~.
- Mỗi node chứa:
- ~count~: số phần tử.
- ~sum~: tổng thực tế các giá trị (không phải giá trị đã nén).
Xử lý truy vấn ~[l, r]~:
- Tìm median trong đoạn ~x_l~ đến ~x_r~ bằng cách truy cập ~PST_r~ và ~PST_{l-1}~.
Dùng PST để tính các thông tin sau:
- median của mảng: ~val~.
- ~cntL~: số phần tử ~\leq~ ~val~.
- ~sumL~: tổng các phần tử ~\leq~ ~val~.
- ~cntR = total - cntL~
- ~sumR = totalSum - sumL~
Dựa vào các thông tin trên có thể tính được đáp án
Độ phức tạp: ~O(q \cdot \log n)~ sau khi xây dựng cây trong ~O(n \log n)~.
Bình luận