DHBB 2024 - CBH - 10 - Cặp đảo ngược
Xem dạng PDFTrong 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