Hướng giải của Tìm Min Và Đếm Tần Suấ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.
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
Bài toán tìm giá trị nhỏ nhất trong đoạn con và đếm xem giá trị nhỏ nhất đó xuất hiện bao nhiêu lần.
Để giải quyết, ta lưu thông tin phức hợp tại mỗi node của Segment Tree: một cấu trúc Info chứa hai trường:
mn: Giá trị cực tiểu trong đoạn.cnt: Số lần xuất hiện của cực tiểu đó.
Khi gộp thông tin từ hai node con:
- Nếu \(a.mn < b.mn\): Node cha lấy thông tin từ \(a\).
- Nếu \(b.mn < a.mn\): Node cha lấy thông tin từ \(b\).
- Nếu \(a.mn = b.mn\): Node cha nhận giá trị cực tiểu là \(a.mn\) và trường đếm bằng tổng số lần xuất hiện ở cả hai con:
a.cnt + b.cnt.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct Info {
long long mn; int cnt;
};
Info combine(Info a, Info b) {
if(a.mn < b.mn) return a;
if(b.mn < a.mn) return b;
return {a.mn, a.cnt + b.cnt};
}
struct SegTree {
int n; vector<Info> tree;
SegTree(int size) { n = size; tree.assign(4 * n, {(long long)(2e9+7), 0}); }
void update(int node, int start, int end, int pos, long long val) {
if(start == end) { tree[node] = {val, 1}; return; }
int mid = (start + end)/2;
if(pos <= mid) update(2*node, start, mid, pos, val);
else update(2*node+1, mid+1, end, pos, val);
tree[node] = combine(tree[2*node], tree[2*node+1]);
}
Info query(int node, int start, int end, int l, int r) {
if(r < start || end < l) return {(long long)(2e9+7), 0};
if(l <= start && end <= r) return tree[node];
int mid = (start + end)/2;
return combine(query(2*node, start, mid, l, r), query(2*node+1, mid+1, end, l, r));
}
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q; if(!(cin >> n >> q)) return 0;
SegTree st(n);
for(int i=0;i<n;i++) { int x; cin >> x; st.update(1, 0, n-1, i, x); }
while(q--){
int t; cin >> t;
if(t == 1) { int pos; long long val; cin >> pos >> val; st.update(1, 0, n-1, pos-1, val); }
else { int l, r; cin >> l >> r; Info res = st.query(1, 0, n-1, l-1, r-1); cout << res.mn << " " << res.cnt << "\n"; }
}
}
Nhận xét