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
Cuối cùng shizuka cũng đã được giải thoát :))
Vì hạnh phúc của nobita tôi nhất định sẽ giải đc bài này :))))
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Nobita : SAD boy ._. ..............
Bài nghe đau tim cho Nobita thế :))
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.