Độ xáo trộn của bảng xếp hạng
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một bảng xếp hạng gồm $N$ phần tử $a_1, a_2, \dots, a_N$. Một cặp $(i, j)$ được gọi là cặp nghịch thế nếu $i < j$ và $a_i > a_j$. Hãy dùng thuật toán sắp xếp trộn (Merge Sort) để đếm tổng số cặp nghịch thế của dãy.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$.
Dữ liệu ra
Một số nguyên duy nhất là số cặp nghịch thế.
Ví dụ
| Input | Output |
|---|---|
| 5 2 4 1 3 5 |
3 |
| 4 4 3 2 1 |
6 |
Giới hạn
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$
Community Discussion