DHBB 2024 - CBH - 10 - Cặp đảo ngược

Xem dạng PDF

Gửi bài giải

Điểm: 35,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

An là một cậu bé thông minh và rất yêu thích Toán học. Một buổi sáng cậu đang chơi với một dãy số nguyên thì cậu chợt nảy ra một ý tưởng. Cậu muốn biết trong dãy số đang có thì có bao nhiêu cặp ~(i, j)~ sao cho ~i > j~ thì ~a_i < a_j~ với mọi ~j = 0, 1, \dots, n - 1~. Biết rằng với mỗi ~j = 0, 1, \dots, n - 1~, dãy ban đầu sẽ biến đổi theo quy tắc, tất cả các ~a_i~ có giá trị lớn hơn ~j~ sẽ được giảm về giá trị ~j~.

Input

  • Dòng 1: Chứa số nguyên ~n~.

  • Dòng 2: Chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Output

Gồm ~n~ dòng là số lượng cặp đảo ngược tương ứng với các giá trị ~j = 0, 1, \dots, n - 1~.

Scoring

  • ~1 \le n \le 10^5~.

  • ~0 \le a_i \le n~.

Subtask Điểm Ràng buộc
1 ~20\%~ ~n \le 100~
2 ~30\%~ ~n \le 5000~
3 ~50\%~ Không có giới hạn gì thêm

Sample Input 1

5
5 2 3 3 0

Sample Output 1

0
4
4
5
7

Notes

Dòng thứ ~4~ của kết quả là số lượng cặp đảo ngược khi ~j = 3~. Khi đó dãy ban đầu ~a~ sẽ trở thành ~\{3, 2, 3, 3, 0\}~ và có số lượng cặp đảo ngược bằng ~5~: ~a_1 > a_2~, ~a_1 > a_5~, ~a_2 > a_5~, ~a_3 > a_5~ và ~a_4 > a_5~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


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