Hướng giải của Vị Trí Đầu Tiên Của Min
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.
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ả:
Hướng dẫn giải
Sparse Table có thể lưu cặp (giá trị, chỉ số) thay vì chỉ giá trị. Khi hợp nhất hai đoạn, ta chọn cặp có giá trị nhỏ hơn; nếu bằng nhau, chọn chỉ số nhỏ hơn.
Xây dựng \(st[k][i]\) lưu cặp \((giá\_trị\_nhỏ\_nhất, chỉ\_số)\) của đoạn \(2^k\).
Truy vấn \((l, r)\): lấy hai đoạn \([l, l+2^k-1]\) và \([r-2^k+1, r]\), so sánh để tìm cặp thoả mãn.
Độ phức tạp: Tiền xử lý \(O(N \log N)\), mỗi truy vấn \(O(1)\).
Mã nguồn C++
// Giải thuật st cho bài toán st-first-min-idx\n#include <bits/stdc++.h>
using namespace std;
const int LOG = 17;
int main() {
// Doc du lieu dau vao
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q; cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<vector<pair<int,int>>> st(LOG, vector<pair<int,int>>(n));
for (int i = 0; i < n; i++) st[0][i] = {a[i], i};
// Duyet qua tung phan tu
for (int k = 1; k < LOG; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
auto left = st[k - 1][i];
auto right = st[k - 1][i + (1 << (k - 1))];
if (left.first < right.first) st[k][i] = left;
else if (right.first < left.first) st[k][i] = right;
else st[k][i] = (left.second < right.second) ? left : right;
}
}
vector<int> lg(n + 1);
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
while (q--) {
int l, r; cin >> l >> r; l--; r--;
int k = lg[r - l + 1];
auto left = st[k][l];
auto right = st[k][r - (1 << k) + 1];
int ans;
if (left.first < right.first) ans = left.second;
else if (right.first < left.first) ans = right.second;
else ans = min(left.second, right.second);
cout << ans + 1 << "\n";
}
}
Nhận xét