Hướng giải của Tìm Điểm Nhỏ Thứ K

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 yêu cầu tìm phần tử nhỏ thứ \(K\) trong một tập hợp biến động. Ta áp dụng kỹ thuật Binary Lifting trên Fenwick Tree:

Fenwick Tree quản lý số lượng phần tử xuất hiện của từng giá trị.
Tổng tiền tố tại \(X\) là số lượng số nhỏ hơn hoặc bằng \(X\). Việc tìm số nhỏ thứ \(K\) tương ứng với tìm \(X\) sao cho tổng tiền tố đạt ít nhất là \(K\).
Ta duyệt từ bit lớn nhất xuống bit nhỏ nhất, dịch chuyển chỉ số idx nếu tổng tích lũy vẫn nhỏ hơn \(K\). Kỹ thuật này giúp tìm ra \(X\) trong thời gian \(O(\log(\text{MAX\_VAL}))\), tối ưu hơn nhiều so với tìm kiếm nhị phân thông thường \(O(\log^2(\text{MAX\_VAL}))\).

Mã nguồn C++ mẫu

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

const int MAX_VAL = 100005;
vector<int> bit(MAX_VAL + 2, 0);
int total_elements = 0;

void update(int i, int val) {
    for (; i <= MAX_VAL; i += i & -i) bit[i] += val;
}

int find_kth(int k) {
    if (k > total_elements) return -1;
    int idx = 0;
    for (int sz = 1 << 17; sz > 0; sz >>= 1) {
        if (idx + sz <= MAX_VAL && bit[idx + sz] < k) {
            idx += sz;
            k -= bit[idx];
        }
    }
    return idx + 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q; if (!(cin >> q)) return 0;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int val; cin >> val;
            update(val, 1);
            total_elements++;
        } else {
            int k; cin >> k;
            cout << find_kth(k) << "\n";
        }
    }
}

Nhận xét

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