trang chủ / bài tập / elefarr

Đếm số xuất hiện đúng bằng giá trị

Cho dãy $a$ gồm $n$ số nguyên dương, đánh số từ $1$ đến $n$ .

Bạn nhận được $m$ truy vấn, mỗi truy vấn là một cặp $(l, r)$ . Với mỗi truy vấn, hãy đếm xem có bao nhiêu giá trị $x$ thoả mãn: $x$ xuất hiện đúng $x$ lần trong đoạn $a_{l}, a_{l + 1}, \dots, a_{r}$ .

Mỗi giá trị $x$ chỉ được tính một lần, bất kể nó xuất hiện bao nhiêu lần.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ : độ dài dãy và số truy vấn.
Dòng thứ hai chứa $n$ số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ .
$m$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $l_{j}$ và $r_{j}$ mô tả truy vấn thứ $j$ .

Dữ liệu ra

In ra $m$ dòng, dòng thứ $j$ là đáp án cho truy vấn thứ $j$ .

Ràng buộc

$1 \leq n, m \leq 10^{5}$
$1 \leq a_{i} \leq 10^{9}$
$1 \leq l_{j} \leq r_{j} \leq n$

Ví dụ

Input	Output	Giải thích
7 2 3 1 2 2 3 3 7 1 7 3 4	3 1	Truy vấn $(1, 7)$ xét cả dãy: $1$ xuất hiện $1$ lần, $2$ xuất hiện $2$ lần, $3$ xuất hiện $3$ lần, nên có $3$ giá trị thoả mãn. Giá trị $7$ chỉ xuất hiện $1$ lần nên không tính. Truy vấn $(3, 4)$ xét đoạn $2 2$ : chỉ có $x = 2$ thoả mãn.
6 6 1 2 2 3 3 3 1 2 2 2 1 3 2 4 4 6 1 6	1 0 2 1 1 3	Truy vấn $(2, 2)$ xét đoạn $2$ : giá trị $2$ chỉ xuất hiện $1$ lần chứ không phải $2$ lần, nên đáp án là $0$ . Truy vấn $(2, 4)$ xét đoạn $2 2 3$ : chỉ $x = 2$ thoả mãn. Truy vấn $(1, 6)$ xét cả dãy nên cả $1$ , $2$ , $3$ đều thoả mãn.

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 6,00một phần

Giới hạn thời gian 2.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, F#, Forth, Fortran, Go, Groovy, Java, Javascript, Julia, Kotlin, Lean, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, Swift, TCL, Typescript, V, Visual Basic, Zig

Đề bài

Mô tả

Dữ liệu vào

Dữ liệu ra

Ràng buộc

Ví dụ

Bình luận