Hướng giải của Đếm Số Nhỏ Hơn Hoặc Bằng X

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 Số Nhỏ Hơn Hoặc Bằng X

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

Yêu cầu đếm số lượng phần tử \(\le X\) trên đoạn \([L, R]\). Sử dụng Wavelet Tree, tại mỗi nút quản lý khoảng \([lo, hi]\) với \(mid = (lo + hi)/2\):

  • Nếu đoạn cần tìm \([L, R]\) trống rỗng hoặc \(X < lo\), kết quả tại nhánh này là 0.
  • Nếu \(hi \le X\), toàn bộ các phần tử trong đoạn \([L, R]\) tại nút hiện tại đều thỏa mãn \(\le X\). Ta trả về số phần tử của đoạn là \(R - L + 1\).
  • Ngược lại, ta đệ quy xuống cả hai con trái và phải:
    • Con trái quản lý phạm vi \([lo, mid]\): đoạn con tương ứng là \([B[L-1]+1, B[R]]\).
    • Con phải quản lý phạm vi \([mid+1, hi]\): đoạn con tương ứng là \([L - B[L-1], R - B[R]]\).
    • Kết quả là tổng của hai nhánh con.
Độ phức tạp
  • Thời gian: \(O(\log(max\_val - min\_val))\) mỗi truy vấn.
  • Không gian: \(O(N \log(max\_val - min\_val))\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

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<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> temp = a;
    int minVal = *min_element(temp.begin(), temp.end());
    int maxVal = *max_element(temp.begin(), temp.end());
    WaveletTree wt(temp.begin(), temp.end(), minVal, maxVal);

    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        cout << wt.countLessEq(l, r, x) << "\n";
    }
    return 0;
}

Nhận xét

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