Lời nguyền của Shizuka

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
a520huynm
Dạng bài
Đ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