Độ xáo trộn của bảng xếp hạng

Buổi 05 — Hàm & Đệ quy Buổi 06 — Sắp xếp & Tìm kiếm Buổi 08 — Contest Chặng 1 sorting
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved