Bài này mình ra đề từ thời thi VNOI Marathon 2012, hôm nay lục lại máy tính thấy có lời giải, nên đăng lại lên đây để các bạn tham khảo.
Tóm tắt lại đề bài:
Cho N điểm, điểm thứ i có tọa độ (xi, yi).
Cho Q truy vấn, mỗi truy vấn thuộc 2 dạng:
Đổi vị trí điểm thứ i
Cho điểm (X, Y). Yêu cầu tính sum( max( X-xi, Y-yi ) ).
Với a1, a2 khác 0, bài toán trở nên khó hơn một chút, do các bạn buộc phải trả xử lý online.
Hướng giải:
Bài này được mình cải tiến từ bài VNOI - POINT. Thông thường, với bài toán chứa dấu giá trị tuyệt đối, cách làm là tách riêng theo từng thành phần tọa độ, rồi phá dấu trị tuyệt đối bằng cách xét tính âm dương của biểu thức. Trong bài này, phần khó nhất là không thể tách được hàm sum(max(X-xi, Y-yi)) riêng theo từng trục x, y. Lời giải của ban tổ chức và các thí sinh được lớn hơn 50 điểm đều dùng phương pháp chuyển hệ tọa độ (x, y) thành (x+y, x-y), từ đó thu được hàm khoảng cách mới có thể tách theo từng thành phần tọa độ.
Cụ thể hơn:
30% test đầu tiên
Để qua được 30% test đầu tiên, bạn chỉ cần viết 1 chương trình duyệt thông thường với độ phức tạp O(N*Q). (Giới hạn thời gian khá lớn, nên bạn cũng có thể được 40% test).
50% test tiếp theo
Để qua được 50% test tiếp theo, trước hết cần giải bài toán đơn giản hơn:
- N người đứng im
- Heo chỉ di chuyển theo 4 hướng (không di chuyển chéo).
Trong bài toán đơn giản hơn này, khoảng cách giữa 2 điểm (x1, y1) và (x2, y2) là:
|x1 - x2| + |y1 - y2|.
Gọi vị trí của heo là (X,Y), vị trí N người là (xi, yi). Ta cần tính tổng:
sum( |X - xi| + |Y - yi| ), i = 1..N
= sum( |X - xi|) + sum( |Y - yi| )
--> Ta có thể xử lý riêng từng chiều x, y.
Xét chiều x, sau khi phá dấu giá trị tuyệt đối, bài toán được đưa về chặt nhị phân thông thường: Cho mảng tọa độ x, với một số nguyên X, bạn cần tính tổng các số nhỏ hơn X, tổng các số lớn hơn X, số lượng số nhỏ hơn X và số lượng số lớn hơn X.
Bằng việc nhận xét rằng việc di chuyển theo đường chéo thường tốt hơn theo đường thẳng, các bạn có thể chuyển bài toán 8 hướng về 4 hướng sau khi quay điểm (x,y) thành (x+y, x-y).
Để thực hiện thao tác di chuyển người & truy vấn, cần chú ý rằng a1 = a2 = 0, do đó ta có thể tính trước tọa độ tất cả các điểm, từ đó có thể rời rạc hóa & dùng 1 cấu trúc dữ liệu, chẳng hạn interval tree để lưu trữ thông tin của N người.
10% test tiếp theo
Để qua được 10% tiếp theo, vì tọa độ <= 10^6, nên dù không cần rời rạc hóa, bạn vẫn có thể dùng interval tree (hoặc các cấu trúc tương tự) để lưu trữ thông tin của N người.
10% test cuối cùng
Để qua được 10% test cuối cùng, có 2 cách chính:
1. Dùng Cây tìm kiếm nhị phân cân bằng để lưu trữ thông tin.
2. Dùng interval tree, với cấp phát bộ nhớ động. Chú ý là số nút trên cây cần truy cập vào là O(Nlog(BASE)), nên bộ nhớ cần cấp phát cũng chỉ là O(Nlog(BASE)).
2 test cuối có giới hạn N, Q nhỏ hơn. Lý do: interval tree và một số loại cây nhị phân có tốc độ chạy chậm, khó có thể qua được giới hạn 10^5. Mình cố tình đặt giới hạn thời gian để code interval tree và splay tree bị mất từ 2 - 4 test (Lời giải của bạn darksabers dùng interval tree bị mất 4 test). Muốn chắc chắn qua được 100% test với cấu trúc dữ liệu (CTDL) chậm, bạn cần cài cả cách offline và online cho bài này. Tuy nhiên, 1 số CTDL có tốc độ nhanh hơn có thể qua được tất cả các test, ví dụ: treap (yenthanh132), red black tree (langtrunghieu (nick thi VM12 là heroes) - khá tiếc là bạn này cài red black tree vô cùng kỹ thuật nhưng do bị quên mod 1 chỗ nên bị tràn số và sai 2 test)
