Subtask 1

Giả sử hai tập được chọn là ~A~ và ~B~. Gọi điểm chung của các đoạn của tập ~A~ là ~x~ và điểm chung của các đoạn trong tập ~B~ là ~y~ (các điểm ~x~, ~y~ chỉ cần quan tâm tới các điểm đầu mút của mỗi đoạn). Duyệt ~x~, ~y~ và duyệt các đoạn để đếm số đoạn chỉ chứa ~x~, số đoạn chỉ chứa ~y~ và số đoạn chứa cả ~x~ lẫn ~y~ và tìm ra kết quả.

Độ phức tạp: ~Ο~ ~(N^3)~.

Subtask 2

Thay vì phải duyệt các đoạn để đếm số đoạn chỉ chứa ~x~, số đoạn chỉ chứa ~y~ và số đoạn chứa cả ~x~ lẫn ~y~, dùng hai mảng cộng dồn ~TL[u]~ là số đoạn có ~l_i ≤ u~ và ~TR[u]~ là số đoạn có ~r_i < u~ để tính số đoạn chứa điểm ~u~ sẽ là ~TL[u]~ ~–~ ~TR[u]~.

Độ phức tạp: ~Ο~ ~(N^2)~.

Subtask 3

Tìm kiếm nhị phân kết quả, với giá trị ~mid~, ta cần tìm hai vị trí ~x~, ~y~ mà có thể tìm được ~mid~ đoạn phủ lên. Sweep line ~x~, ta sẽ chọn ~mid~ đoạn chứa ~x~ có ~r_i~ nhỏ nhất, các đoạn còn lại sử dụng một cây segment tree để biết được mỗi điểm ~y~ có bao nhiêu đoạn đang phủ lên, nếu tồn tại một vị trí ~y ≥ mid~ đoạn phủ lên thì tồn tại cách chọn.

Độ phức tạp: ~Ο~ ~(N \times log^2 ⁡N~).

Subtask 4

Tương tự như subtask 3, nhưng thay vì phải tìm kiếm nhị phân, ta sẽ sử dụng two pointer để tịnh tiến kết quả.

Độ phức tạp: ~Ο~ ~(N \times log ⁡N~).