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 số cặp nghịch thế bằng merge sort

    Cho dãy a0,…,an−1a_0,\dots,a_{n-1}a0​,…,an−1​. Đếm số cặp nghịch thế: số cặp chỉ số (i,j)(i, j)(i,j) với i<ji < ji<j nhưng ai>aja_i > a_jai​>aj​. Dùng kỹ thuật chia để trị (merge sort) để đạt O(nlog⁡n)O(n\log n)O(nlogn).

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

      Dòng đầu: nnn. Dòng hai: nnn số aia_iai​.

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

      1≤n≤5⋅1051 \le n \le 5\cdot10^51≤n≤5⋅105, ∣ai∣≤109|a_i| \le 10^9∣ai​∣≤109.

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

      Một số nguyên: số cặp nghịch thế.

    Ví dụ:

    Đầu vào:

    5
3 1 2 5 4

    Đầu ra:

    3

    Giải thích:

    Các cặp nghịch thế: (3,1),(3,2),(5,4) — đúng 3 cặp.

    Đang tải editor...