## Bài toán yêu cầu bạn tìm số lần giá trị $x$ xuất hiện trong đoạn $[l, r]$ trong $q$ truy vấn.
## Một hướng giải là lập bảng lưu lại vị trí xuất hiện của từng giá trị trong mảng, với mỗi truy vấn xác định khoảng xuất hiện nhỏ nhất mà vẫn bao trùm đoạn đã cho, từ đó sẽ có được số lần xuất hiện giá trị cần tìm. Có thể giải như sau:
- Khởi tạo một bảng tần số, để lưu lại vị trí xuất hiện của mỗi giá trị $i$ trong mảng ban đầu. Ví dụ bạn có mảng $[1, 1, 2, 3, 1, 2, 3, 2]$, bảng lúc này sẽ kiểu như:
$f[1] = [1, 2, 5]$\
$f[2] = [3, 6, 8]$\
$f[3] = [4, 7]$.
*(như giá trị $1$ xuất hiện lần thứ nhất ở chỉ số $1$, lần thứ thứ ba ở chỉ số $5$,...)*
- Truy vấn cho bạn một đoạn $[l, r]$, lúc này bạn sử dụng **chặt nhị phân** để tìm chỉ số $ll$ nhỏ nhất sao cho $ll >= l$, và chỉ số $rr$ lớn nhất thỏa mãn $rr <= r$ . Có hai hướng để thực hiện:
**1.** Sử dụng lần lượt hàm **lower_bound** và **upper_bound** để tìm và đầu $ll$ và $rr$. Thuận tiện để tìm trong C++.
**2.** Chặt nhị phân "nguyên thủy" bằng đầu $L$ và $R$. Liên tiếp chia đôi khoảng tìm kiếm bằng $ M = \frac{L + R}{2} $ cho đển khi tìm được chỉ số thỏa mãn cho $ll$ và $rr$. Sẽ tương đối phức tạp hơn vì phải kéo các đầu chính xác.
- Sau khi bạn đã tìm được hai đầu cần thiết, đối chiếu với chỉ số trên bảng tần số, đáp án của truy vấn sẽ là hiệu của **số lần xuất hiện đến đuôi** và **số lần xuất hiện đến đầu**.
### Code tham khảo:
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int LIM = 1e5 + 5;
int n, q, shelf[LIM];
map <int, vector <int>> f;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> shelf[i];
int num = shelf[i];
if (f[num].empty()) f[num].push_back(0);
f[num].push_back(i);
}
int qq = q;
while (q--) {
if (q < qq - 1) cout << endl;
int l, r, x;
cin >> l >> r >> x;
int L, R, M, ll, rr;
L = 1, R = f[x].size() - 1;
while (L <= R) {
M = (L + R) / 2;
if (f[x][M] >= l) R = M - 1;
else L = M + 1;
}
ll = L;
L = 1, R = f[x].size() - 1;
while (L <= R) {
M = (L + R) / 2;
if (f[x][M] <= r) L = M + 1;
else R = M - 1;
}
rr = R;
cout << (ll > rr ? 0 : (rr - ll + 1));
}
}
```
noice
Created at
4 likes