Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Đếm cặp đảo ngược

    Cho một dãy gồm nnn số nguyên a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​. Một cặp đảo ngược (nghịch thế) là một cặp chỉ số (i,j)(i, j)(i,j) sao cho i<ji < ji<j nhưng ai>aja_i > a_jai​>aj​.

    Số cặp đảo ngược cho biết dãy "xa" trạng thái sắp xếp tăng dần đến mức nào. Hãy đếm tổng số cặp đảo ngược của dãy.

    Vì số lượng có thể rất lớn, hãy chú ý dùng thuật toán hiệu quả (ví dụ chia để trị kết hợp trộn — merge sort) thay vì duyệt mọi cặp.

    • Định dạng đầu vào:

      Dòng đầu chứa số nguyên nnn. Dòng thứ hai chứa nnn số nguyên cách nhau bởi dấu cách.

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105, −109≤ai≤109-10^9 \le a_i \le 10^9−109≤ai​≤109.

    • Định dạng đầu ra:

      In ra một số nguyên duy nhất là số cặp đảo ngược.

    Ví dụ:

    Đầu vào:

    5
2 4 1 3 5

    Đầu ra:

    3

    Giải thích:

    Các cặp đảo ngược: (2,1),(4,1),(4,3) → 3 cặp.

    Đang tải editor...