Hiểu bài toán

Bài toán yêu cầu tìm số lượng đoạn thẳng ít nhất để chọn sao cho chúng bao phủ hoàn toàn một đoạn [a, b] cho trước. Với mỗi truy vấn (a, b), chúng ta cần tìm một dãy con các đoạn thẳng sao cho:

1. Đoạn thứ nhất bắt đầu tại hoặc trước 'a'.
2. Đoạn cuối cùng kết thúc tại hoặc sau 'b'.
3. Các đoạn liên tiếp trong dãy phải có giao nhau (tức là đoạn sau phải bắt đầu trước hoặc ngay sau khi đoạn trước kết thúc). Đây là bài toán tìm đường đi ngắn nhất trên đồ thị hoặc bài toán 'Jumping Game' biến thể.

Các cách tiếp cận

Cách Bộ lọc Greedy (Lọc đoạn thẳng dư thừa)

https://ideone.com/fork/9b3d0f

• Time Complexity: O(N log N + Q * N) - Qúa chậm cho Q lớn
• Space Complexity: O(N)

Phương pháp này là nền tảng cho các giải pháp tối ưu. Đầu tiên, ta sắp xếp các đoạn thẳng theo tọa độ bắt đầu (L). Sau đó, ta lọc các đoạn thẳng bằng cách giữ lại những đoạn có R lớn hơn R của đoạn trước đó. Điều này đảm bảo ta có một dãy các đoạn thẳng với L tăng dần và R tăng dần.

Với mỗi truy vấn [a, b], ta có thể thử duyệt qua các đoạn thẳng còn lại (sau khi lọc) để tìm cách bao phủ [a, b]. Tuy nhiên, nếu chỉ dùng cách này mà không có cấu trúc dữ liệu hỗ trợ, độ phức tạp sẽ là O(Q*N), không khả thi.

Cách Mảng nhảy (Sparse Table / Jumping Array)

https://ideone.com/fork/3b1c9d

• Time Complexity: O(N log N + Q log N)
• Space Complexity: O(N log N)

Đây là giải pháp tối ưu.

1. Lọc dữ liệu (Preprocessing): Sắp xếp và loại bỏ các đoạn thẳng bị che phủ (không dùng đến). Kết quả là một danh sách các đoạn có L tăng dần và R tăng dần.
2. Xây dựng Mảng Nhảy (Jumping Table): Dùng kỹ thuật Binary Lifting (Tăng tốc nhảy). up[k][i] là vị trí của đoạn thẳng sau khi nhảy 2^k bước từ đoạn i. Để tính up[0][i], ta cần tìm đoạn j xa nhất sao cho useful[j].l <= useful[i].r. Do useful đã được sắp xếp và lọc, ta có thể dùng con trỏ trượt (two pointers) để tính mảng này trong O(N).
3. Trả lời truy vấn: Với mỗi truy vấn [a, b], ta dùng binary search để tìm đoạn bắt đầu phù hợp nhất che phủ a. Sau đó, dùng mảng nhảy để nhảy nhanh đến đoạn cuối cùng mà vẫn chưa vượt quá b. Số bước nhảy cộng thêm 1 (hoặc 2) chính là kết quả.

Cách Binary Search trên mảng nhảy (Sparse Table)

https://ideone.com/fork/5e1f2a

• Time Complexity: O((N+Q) log N)
• Space Complexity: O(N log N)

Giải pháp này tương tự như 'Mảng nhảy' nhưng nhấn mạnh vào việc sử dụng Binary Lifting để trả lời truy vấn một cách hiệu quả. Logic cơ bản:

1. Lọc và sắp xếp đoạn thẳng.
2. Tạo mảng jump[i] đại diện cho bước nhảy greediest (điểm đến tốt nhất trong 1 bước).
3. Xây dựng bảng up[k][i] (Sparse Table) cho phép nhảy 2^k bước.
4. Với mỗi truy vấn, tìm đoạn bắt đầu. Sau đó, duyệt từ bit cao nhất xuống thấp nhất của số bước nhảy. Nếu nhảy 2^k bước mà vẫn chưa chạm tới b (tức R của đoạn đích vẫn < b), ta thực hiện nhảy và cộng dồn số bước.
5. Kết quả là số bước đã cộng dồn + 1 (hoặc 2 tùy vào cách đếm).

Lưu ý quan trọng: Đoạn bắt đầu chỉ cần che phủ a (L <= a <= R). Các đoạn tiếp theo chỉ cần giao nhau (L <= R_prev + 1).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phép lọc (Filtering): Sau khi sắp xếp theo L, ta chỉ cần giữ lại các đoạn thẳng mà R của chúng lớn hơn R của đoạn trước đó. Các đoạn bị loại bỏ không bao giờ là lựa chọn tối ưu trong bài toán này.
• Chiến lược Greedy: Để bao phủ một đoạn [x, y], cách tốt nhất là chọn đoạn bắt đầu trước hoặc tại x và kéo dài xa nhất có thể. Bước tiếp theo nên chọn đoạn bắt đầu trước khi đoạn trước kết thúc và kéo dài xa nhất có thể.
• Binary Lifting: Kỹ thuật này biến độ phức tạp truy vấn từ O(N) xuống O(log N) bằng cách precompute các bước nhảy có độ dài lũy thừa 2.

Lỗi thường gặp

• Xử lý biên: Các đoạn thẳng có thể bắt đầu hoặc kết thúc cùng tọa độ. Cần chú ý khi so sánh <= hay <.
• Bắt đầu truy vấn: Đoạn bắt đầu che phủ 'a' có thể nằm ở chỉ số trước chỉ số tìm được bởi lowerbound (do lowerbound tìm đoạn bắt đầu >= a).
• Kiểm tra khả thi: Cần kiểm tra xem có đoạn thẳng nào che phủ được 'a' không trước khi bắt đầu nhảy. Nếu không, đáp án là -1.