Hướng giải của Liệt Kê Các Đ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: Liệt Kê Các Đoạn Giao Nhau

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

Bài toán yêu cầu liệt kê toàn bộ các đoạn thẳng giao với đoạn truy vấn \([A, B]\). Sử dụng cấu trúc dữ liệu Interval Tree:

  • Khi truy vấn đoạn \([A, B]\) trên một nút của cây:
    • Nếu \(B < median\): ta duyệt danh sách \(S_1\) (sắp xếp tăng theo mút trái \(L_i\)), dừng lại ngay khi gặp phần tử có \(L_i > B\). Với các phần tử hợp lệ (\(L_i \le B\)), ta tích lũy kết quả. Tiếp tục đệ quy sang nhánh con bên trái.
    • Nếu \(A > median\): ta duyệt danh sách \(S_2\) (sắp xếp giảm theo mút phải \(R_i\)), dừng lại ngay khi gặp phần tử có \(R_i < A\). Với các phần tử hợp lệ (\(R_i \ge A\)), ta tích lũy kết quả. Tiếp tục đệ quy sang nhánh con bên phải.
    • Nếu \([A, B]\) chứa median: toàn bộ danh sách ở giữa tại nút hiện tại đều giao với \([A, B]\). Ta lấy toàn bộ chúng và đệ quy xuống cả hai con trái và phải.
  • Để tránh ghi file kết quả quá lớn, ta chỉ xuất ra số lượng đoạn giao và một checksum đại diện cho tổng của tích \(L_i \times R_i \pmod{10^9+7}\).
Độ phức tạp
  • Thời gian: \(O(N \log N)\) xây cây. Mỗi truy vấn mất \(O(\log N + k)\) với \(k\) là số lượng đoạn giao được liệt kê.
  • 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);
    }

    void query(Node* node, int a, int b, int& count, long long& sum_val) {
        if (!node) return;
        const int MOD = 1e9 + 7;
        if (b < node->median) {
            for (auto& seg : node->S1) {
                if (seg.first <= b) {
                    count++;
                    long long term = (1LL * (seg.first % MOD + MOD) % MOD * ((seg.second % MOD + MOD) % MOD)) % MOD;
                    sum_val = (sum_val + term) % MOD;
                }
                else break;
            }
            query(node->left, a, b, count, sum_val);
        } else if (a > node->median) {
            for (auto& seg : node->S2) {
                if (seg.second >= a) {
                    count++;
                    long long term = (1LL * (seg.first % MOD + MOD) % MOD * ((seg.second % MOD + MOD) % MOD)) % MOD;
                    sum_val = (sum_val + term) % MOD;
                }
                else break;
            }
            query(node->right, a, b, count, sum_val);
        } else {
            for (auto& seg : node->S1) {
                count++;
                long long term = (1LL * (seg.first % MOD + MOD) % MOD * ((seg.second % MOD + MOD) % MOD)) % MOD;
                sum_val = (sum_val + term) % MOD;
            }
            query(node->left, a, b, count, sum_val);
            query(node->right, a, b, count, sum_val);
        }
    }
};

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;
        int count = 0;
        long long sum_val = 0;
        tree.query(tree.root, a, b, count, sum_val);
        cout << count << " " << sum_val << "\n";
    }
    return 0;
}

Nhận xét

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