DCT05 – Đếm cặp ngược thứ tự
Xem dạng PDF
Mã bài:
dct05
Điểm:
2 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Đề bài
Một cặp nghịch thế là cặp vị trí (i, j) với i < j nhưng ai > aj. Cho n số nguyên, hãy đếm tổng số cặp nghịch thế.
Do kết quả có thể lớn hơn 2^31−1, hãy sử dụng kiểu số nguyên 64-bit.
Dữ liệu vào
Dòng 1: Số nguyên n. Dòng 2: n số nguyên a1, a2, ..., an.
Dữ liệu ra
In số cặp (i, j) thỏa 1 ≤ i < j ≤ n và ai > aj.
Ràng buộc
1 ≤ n ≤ 200000; -10^9 ≤ ai ≤ 10^9.
Ví dụ
Ví dụ 1
Input
4
4 1 3 2
Output
4
Giải thích: Các cặp nghịch thế: (4,1), (4,3), (4,2), (3,2).
Ví dụ 2
Input
4
2 2 2 2
Output
0
Giải thích: Hai phần tử bằng nhau không tạo thành nghịch thế.
Bình luận