### Quá Trình Nén Tọa Độ: Giả sử bạn có một số tọa độ từ các đoạn (ranges) và các truy vấn (queries), và mục tiêu của bạn là nén các tọa độ này thành các chỉ số trong một phạm vi nhỏ hơn. Quá trình này có thể được chia thành các bước như sau: ### Bước 1: Tạo tập hợp các điểm (points) Tập hợp này sẽ bao gồm tất cả các giá trị từ các đoạn (left, right) và các truy vấn (queries). Lý do bạn cần phải làm điều này là để lấy tất cả các điểm quan trọng cần nén. ```python ranges = [(1, 5), (3, 7), (10, 12)] # Các đoạn hợp lệ queries = [4, 6, 11] # Các truy vấn points = set() # Thêm các điểm từ các đoạn vào tập hợp for left, right in ranges: points.add(left) points.add(right + 1) # +1 để giảm sau đoạn # Thêm các điểm từ các truy vấn vào tập hợp for z in queries: points.add(z) print("Các điểm gốc:", points) ``` **Output**: ``` Các điểm gốc: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} ``` ### Bước 2: Sắp xếp các điểm Sau khi thu thập tất cả các điểm quan trọng, bạn sắp xếp chúng theo thứ tự tăng dần. Điều này sẽ giúp bạn ánh xạ các giá trị gốc vào chỉ số trong một phạm vi nhỏ hơn. ```python sorted_points = sorted(points) print("Các điểm sau khi sắp xếp:", sorted_points) ``` **Output**: ``` Các điểm sau khi sắp xếp: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] ``` ### Bước 3: Ánh xạ giá trị gốc sang chỉ số nén Bây giờ, bạn ánh xạ mỗi điểm gốc vào một chỉ số trong dãy số liên tiếp (nén các tọa độ). Bạn sẽ tạo một từ điển (`compressed`) mà trong đó khóa là các tọa độ gốc và giá trị là các chỉ số tương ứng. ```python compressed = dict() for i in range(len(sorted_points)): compressed[sorted_points[i]] = i + 1 # Chỉ số bắt đầu từ 1 print("Tọa độ nén:", compressed) ``` **Output**: ``` Tọa độ nén: {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11, 12: 12} ``` ### Bước 4: Sử dụng các chỉ số nén để xử lý Giờ đây, các tọa độ gốc đã được nén vào các chỉ số nhỏ hơn. Bạn có thể dùng các chỉ số này trong các mảng hoặc các phép toán khác mà không cần phải lưu trữ toàn bộ phạm vi lớn của các tọa độ gốc. Ví dụ, bạn có thể sử dụng từ điển `compressed` để đánh dấu phạm vi các đoạn (ranges) và tính prefix sum. ```python # Ví dụ đánh dấu một đoạn với chỉ số nén mark = [0] * (len(sorted_points) + 2) # Mảng đánh dấu left = 3 right = 6 mark[compressed[left]] += 1 mark[compressed[right + 1]] -= 1 print("Mảng đánh dấu:", mark) ``` ### Tổng kết Quá trình nén tọa độ trong đoạn mã của bạn thực hiện các bước sau: 1. **Thu thập các tọa độ quan trọng** (từ các đoạn và các truy vấn). 2. **Sắp xếp các tọa độ** để chuẩn bị cho việc ánh xạ. 3. **Ánh xạ các tọa độ vào chỉ số nén** để giảm kích thước bộ nhớ cần thiết. 4. **Sử dụng các chỉ số nén** trong các phép toán tiếp theo, như đánh dấu các phạm vi và tính prefix sum. Kỹ thuật này giúp tiết kiệm bộ nhớ và tối ưu hóa quá trình tính toán khi xử lý các đoạn và truy vấn trong các bài toán lớn.