Lời nguyền của Shizuka
Xem PDF
Điểm:
300
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Shizuka đã bị dính lời nguyền sẽ kết hôn với Degisuki. Để giải được lời nguyền đó Nobita phải giải quyết bài toán sau. Cho một dãy gồm \(n\) số nguyên không âm \(a_1, a_2, a_3, ..., a_n\). Có \(q\) truy vấn \(x, l, r\), cần tính trong đoạn \(l, r\) số \(x\) xuất hiện bao nhiêu lần. Các bạn hãy giúp Nobita phá bỏ lời nguyền đó nha!!!!
Input
- Dòng đầu tiên chứa 2 số \(n, q (1 \leq n, q \leq 10^5)\)
- Dòng thứ hai gồm \(a_1, a_2, a_3, ..., a_n (1 \leq a_i \leq 10^6)\)
- Gồm \(q\) dòng chứa \(x, l, r (1 \leq x \leq 10^6, 1 \leq l \leq r \leq n)\)
Output
- Ghi ra \(q\) dòng là kết quả mỗi truy vấn
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n \cdot q \leq 10^8\)
- Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm
Example
Test 1
Input
5 5
2 1 5 1 3
4 1 5
1 1 2
2 1 5
1 1 5
5 3 3 Output
0
1
1
2
1
Bình luận
tui sẽ cứu degisuki nên code đây:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
unordered_map<int, vector\<int>> positions;
for (int i = 1; i <= n; i++) {
cin >> a[i];
positions[a[i]].push_back(i);
}
while (q--) {
int x, l, r;
cin >> x >> l >> r;
if (positions.find(x) == positions.end()) {
cout << 0 << endl;
continue;
}
const vector<int>& pos = positions[x];
auto it_l = lower_bound(pos.begin(), pos.end(), l);
auto it_r = upper_bound(pos.begin(), pos.end(), r);
int result = it_r - it_l;
cout << result << endl;
}
return 0;
}
15 bình luận nữa