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ố nghịch thế

    Cho dãy nnn số nguyên. Nghịch thế là cặp chỉ số (i,j)(i, j)(i,j) với i<ji < ji<j nhưng ai>aja_i > a_jai​>aj​. Hãy đếm tổng số nghịch thế (dùng sắp xếp trộn, O(nlog⁡n)O(n \log n)O(nlogn)).

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

      Dòng đầu nnn. Dòng hai gồm nnn số nguyên.

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

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

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

      In một số nguyên: số nghịch thế.

    Ví dụ:

    Đầu vào:

    5
2 3 8 6 1

    Đầu ra:

    5

    Giải thích:

    Các nghịch thế: (2,1),(3,1),(8,6),(8,1),(6,1) -> 5 cặp.

    Đang tải editor...