Hướng giải của Đếm Đoạn Thẳng Bao 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

Bài toán đếm số đoạn bao nhau:

  1. Nén tọa độ của các mút \(R\) của tất cả các đoạn thẳng về đoạn \([1, M]\).
  2. Sắp xếp các đoạn thẳng theo mút \(L\) tăng dần. Nếu \(L\) bằng nhau, sắp xếp theo mút \(R\) giảm dần.
  3. Duyệt ngược danh sách các đoạn thẳng từ cuối lên đầu:
    • Khi duyệt đến đoạn \([L_i, R_i]\), toàn bộ các đoạn thẳng đã duyệt trước đó đều có \(L_j \ge L_i\).
    • Do đó, đoạn \(i\) bao đoạn \(j\) khi và chỉ khi \(R_j \le R_i\).
    • Ta thực hiện truy vấn đếm số lượng mút \(R_j \le R_i\) trên Fenwick Tree, đó chính là kết quả cho đoạn \(i\).
    • Thêm mút \(R_i\) của đoạn hiện tại vào Fenwick Tree.

Độ phức tạp thời gian: \(O(N \log N)\).

Mã nguồn C++ mẫu

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

struct Segment {
    int l, r, id;
    bool operator<(const Segment& other) const {
        if (l == other.l) return r > other.r;
        return l < other.l;
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; if (!(cin >> n)) return 0;
    vector<Segment> segs(n);
    vector<int> coords;
    for (int i = 0; i < n; i++) {
        cin >> segs[i].l >> segs[i].r;
        segs[i].id = i;
        coords.push_back(segs[i].r);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    auto get_compressed = [&](int v) {
        return lower_bound(coords.begin(), coords.end(), v) - coords.begin() + 1;
    };
    int m = coords.size();
    vector<int> bit(m + 2, 0);
    auto update = [&](int i, int val) {
        for (; i <= m; i += i & -i) bit[i] += val;
    };
    auto query = [&](int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    };
    sort(segs.begin(), segs.end());
    vector<int> ans(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        int r_idx = get_compressed(segs[i].r);
        ans[segs[i].id] = query(r_idx);
        update(r_idx, 1);
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i == n - 1 ? "" : " ");
    }
    cout << "\n";
}

Nhận xét

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