Hướng giải của Tồn Tại Đoạn Giao Nhau

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải: Tồn Tại Đoạn Giao Nhau

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

Yêu cầu kiểm tra xem có tồn tại ít nhất một đoạn thẳng giao với \([A, B]\) hay không. Thay vì duyệt qua tất cả các đoạn thẳng, ta có thể xây dựng cấu trúc dữ liệu Interval Tree tĩnh trên tập các đoạn thẳng đầu vào:

  • Tại mỗi nút, tìm median của điểm đầu \(L_i\).
  • Phân hoạch tập đoạn thẳng thành 3 nhóm: trái (mút phải < median), phải (mút trái > median), và giữa (chứa median).
  • Khi truy vấn giao với \([A, B]\):
    • Nếu \(B < median\): chỉ cần kiểm tra xem đoạn con bên trái nhất của nhóm giữa (\(S_1\) sắp xếp theo \(L_i\) tăng dần) có giao với \([A, B]\) hay không. Điều này tương đương với \(L_i \le B\). Nếu có, trả về true ngay lập tức. Ngược lại, đệ quy sang con trái.
    • Nếu \(A > median\): chỉ cần kiểm tra xem đoạn con bên phải nhất của nhóm giữa (\(S_2\) sắp xếp theo \(R_i\) giảm dần) có giao với \([A, B]\) hay không. Điều này tương đương với \(R_i \ge A\). Nếu có, trả về true ngay lập tức. Ngược lại, đệ quy sang con phải.
    • Nếu \([A, B]\) chứa median: vì nhóm giữa của nút hiện tại đều chứa median, nên tất cả chúng chắc chắn giao với \([A, B]\). Ta trả về true ngay lập tức (nếu nhóm giữa không rỗng). Nếu rỗng, đệ quy xuống cả hai con trái và phải.
Độ phức tạp
  • Thời gian: Xây cây \(O(N \log N)\). Mỗi truy vấn kiểm tra sự tồn tại mất tối đa \(O(\log N)\) nhờ cơ chế dừng sớm (early exit) ngay khi tìm thấy giao điểm đầu tiên.
  • Không gian: \(O(N \log N)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

struct IntervalTree {
    struct Node {
        int median;
        vector<pair<int,int>> S1;
        vector<pair<int,int>> S2;
        Node *left = nullptr, *right = nullptr;
    };

    Node* root;

    Node* build(vector<pair<int,int>>& intervals) {
        if (intervals.empty()) return nullptr;
        Node* node = new Node();
        vector<int> lvals;
        for (auto& [l, r] : intervals) lvals.push_back(l);
        sort(lvals.begin(), lvals.end());
        node->median = lvals[lvals.size() / 2];

        vector<pair<int,int>> leftSet, rightSet;
        for (auto& [l, r] : intervals) {
            if (r < node->median) leftSet.push_back({l, r});
            else if (l > node->median) rightSet.push_back({l, r});
            else {
                node->S1.push_back({l, r});
                node->S2.push_back({l, r});
            }
        }
        sort(node->S1.begin(), node->S1.end());
        sort(node->S2.begin(), node->S2.end(), [](auto& a, auto& b) {
            return a.second > b.second;
        });
        node->left = build(leftSet);
        node->right = build(rightSet);
        return node;
    }

    IntervalTree(vector<pair<int,int>>& intervals) {
        root = build(intervals);
    }

    bool hasIntersection(Node* node, int a, int b) {
        if (!node) return false;
        if (b < node->median) {
            if (!node->S1.empty() && node->S1[0].first <= b) return true;
            return hasIntersection(node->left, a, b);
        } else if (a > node->median) {
            if (!node->S2.empty() && node->S2[0].second >= a) return true;
            return hasIntersection(node->right, a, b);
        } else {
            return !node->S1.empty() || hasIntersection(node->left, a, b) || hasIntersection(node->right, a, b);
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<pair<int,int>> intervals(n);
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].first >> intervals[i].second;
    }
    IntervalTree tree(intervals);
    while (q--) {
        int a, b;
        cin >> a >> b;
        if (tree.hasIntersection(tree.root, a, b)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.