Tạo Mex

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một mảng gồm $N$ số nguyên không âm. Bạn có thể thực hiện các thao tác, mỗi thao tác thay đổi một phần tử bất kỳ thành một số nguyên không âm bất kỳ.

Giá trị mex (minimum excludant) của một mảng là số nguyên không âm nhỏ nhất không xuất hiện trong mảng đó.

Với mỗi giá trị $i$ từ $0$ đến $N$ , hãy tìm số thao tác tối thiểu cần thực hiện để mex của mảng bằng đúng $i$ .

Dữ liệu vào

Dòng 1: Số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{5}$ )
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $0 \leq a_{i} \leq N$ )

Dữ liệu ra

In ra $N + 1$ dòng, dòng thứ $i$ (đánh số từ 0) chứa số thao tác tối thiểu để mex bằng $i$ .

Ràng buộc

$1 \leq N \leq 2 \times 10^{5}$
$0 \leq a_{i} \leq N$

Ví dụ

Input	Output	Giải thích
4 2 2 2 0	1 0 3 1 2	Mảng ban đầu là $[2, 2, 2, 0]$ . Để mex = 0: đổi phần tử 0 (1 thao tác). Để mex = 1: không cần đổi vì 1 không có trong mảng. Để mex = 2: cần thêm 0 và 1 rồi xóa hết 2 (3 thao tác). Để mex = 3: đổi một phần tử 2 thành 1 (1 thao tác). Để mex = 4: đổi 2 phần tử thành 1 và 3 (2 thao tác).

Bình luận

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