Hướng giải của Đếm Điểm Trong Hình Chữ Nhật

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: Đếm Điểm Trong Hình Chữ Nhật

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

Bài toán yêu cầu đếm số điểm nằm trong hình chữ nhật giới hạn bởi \(x_1 \le x \le x_2\) và \(y_1 \le y \le y_2\). Ta có thể chuyển đổi bài toán 2D này thành truy vấn đoạn 1D tĩnh bằng cách:

  1. Sắp xếp các điểm tăng dần theo hoành độ \(X\). Lưu danh sách hoành độ đã sắp xếp này vào mảng xs.
  2. Lưu các tung độ tương ứng (theo thứ tự hoành độ đã sắp xếp) vào mảng ys.
  3. Xây dựng cây Wavelet Tree quản lý mảng tung độ ys.
  4. Với mỗi truy vấn \([x_1, x_2] \times [y_1, y_2]\):
    • Sử dụng tìm kiếm nhị phân (std::lower_bound và std::upper_bound trên mảng xs) để tìm ra khoảng chỉ số \([L, R]\) (0-indexed) của tất cả các điểm có hoành độ thỏa mãn \(x_1 \le x \le x_2\).
    • Nếu \(L > R\), kết quả là 0.
    • Ngược lại, ta chỉ cần đếm xem trong đoạn con ys[L..R] có bao nhiêu tung độ thỏa mãn \(y_1 \le y \le y_2\).
    • Số lượng tung độ thỏa mãn trong khoảng là: \[\text{Count}(L+1, R+1, y_2) - \text{Count}(L+1, R+1, y_1 - 1)\] (lưu ý chuyển về 1-indexed cho các chỉ số truy vấn Wavelet Tree).
Độ phức tạp
  • Thời gian: Xây cây \(O(N \log N)\). Mỗi truy vấn thực hiện trong \(O(\log N)\) (gồm 2 lần tìm kiếm nhị phân \(O(\log N)\) và 2 lần truy vấn Wavelet Tree \(O(\log(max\_val - min\_val))\)).
  • Không gian: \(O(N \log N)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return x < other.x;
    }
};

struct WaveletTree {
    int lo, hi;
    vector<int> B;
    WaveletTree *left, *right;

    WaveletTree(vector<int>::iterator from, vector<int>::iterator to, int x, int y)
        : lo(x), hi(y), left(nullptr), right(nullptr) {
        if (from == to || lo == hi) return;
        int mid = lo + (hi - lo) / 2;
        auto f = [mid](int val) { return val <= mid; };
        B.reserve(to - from + 1);
        B.push_back(0);
        for (auto it = from; it != to; it++)
            B.push_back(B.back() + f(*it));
        auto pivot = stable_partition(from, to, f);
        left = new WaveletTree(from, pivot, lo, mid);
        right = new WaveletTree(pivot, to, mid + 1, hi);
    }

    int countLessEq(int l, int r, int k) {
        if (l > r || k < lo) return 0;
        if (hi <= k) return r - l + 1;
        int lb = B[l - 1], rb = B[r];
        return left->countLessEq(lb + 1, rb, k) +
               right->countLessEq(l - lb, r - rb, k);
    }

    ~WaveletTree() { delete left; delete right; }
};

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

    vector<int> ys(n);
    for (int i = 0; i < n; i++) ys[i] = pts[i].y;

    int minVal = *min_element(ys.begin(), ys.end());
    int maxVal = *max_element(ys.begin(), ys.end());
    WaveletTree wt(ys.begin(), ys.end(), minVal, maxVal);

    while (q--) {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;
        int L = lower_bound(xs.begin(), xs.end(), x1) - xs.begin();
        int R = upper_bound(xs.begin(), xs.end(), x2) - xs.begin() - 1;
        if (L > R) {
            cout << 0 << "\n";
        } else {
            cout << wt.countLessEq(L + 1, R + 1, y2) - wt.countLessEq(L + 1, R + 1, y1 - 1) << "\n";
        }
    }
    return 0;
}

Nhận xét

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