Hướng dẫn giải: Đếm Số Lượng Đoạn Giao Nhau

Phân tích bài toán

Yêu cầu đếm số lượng đoạn thẳng giao với \([A, B]\). Ta có nhận xét hình học: một đoạn thẳng \([L_i, R_i]\) giao với \([A, B]\) nếu và chỉ nếu nó không nằm hoàn toàn về phía bên trái của \(A\) (\(R_i < A\)) và không nằm hoàn toàn về phía bên phải của \(B\) (\(L_i > B\)). Do đó: \[\text{Số đoạn giao} = N - \text{Số đoạn có } R_i < A - \text{Số đoạn có } L_i > B\] Ta có thể tính toán hai số lượng đoạn loại trừ này cực nhanh bằng tìm kiếm nhị phân:

• Sắp xếp mảng điểm đầu mút trái \(L\) và mảng điểm đầu mút phải \(R\) độc lập với nhau.
• Số lượng đoạn có \(R_i < A\): là số lượng phần tử nhỏ hơn \(A\) trong mảng \(R\), tìm được qua std::lower_bound trong \(O(\log N)\).
• Số lượng đoạn có \(L_i > B\): là số lượng phần tử lớn hơn \(B\) trong mảng \(L\), tìm được qua std::upper_bound trong \(O(\log N)\). Kết quả cho mỗi truy vấn là \(N - \text{c\_left} - \text{c\_right}\) trong thời gian \(O(\log N)\).

Độ phức tạp

• Thời gian: \(O(N \log N)\) để sắp xếp độc lập hai mảng đầu mút, và \(O(\log N)\) cho mỗi truy vấn.
• Không gian: \(O(N)\) bộ nhớ.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<int> L(n), R(n);
    for (int i = 0; i < n; i++) {
        cin >> L[i] >> R[i];
    }
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());

    while (q--) {
        int a, b;
        cin >> a >> b;
        int count_left = lower_bound(R.begin(), R.end(), a) - R.begin();
        int count_right = L.end() - upper_bound(L.begin(), L.end(), b);
        int ans = n - count_left - count_right;
        cout << max(0, ans) << "\n";
    }
    return 0;
}