Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải: Kệ Thuốc Phép
Hướng tiếp cận
Quy về bài toán đếm nghịch thế (inversion counting) bằng cách xây dựng hoán vị từ thứ hạng tương đối.
Nhận xét quan trọng
Tổng sai lệch nhỏ nhất khi hai dãy có cùng thứ tự tương đối: phần tử nhỏ nhất của ghép với phần tử nhỏ nhất của , nhỏ thứ hai với nhỏ thứ hai, v.v. Điều này được chứng minh bằng bất đẳng thức sắp xếp lại (rearrangement inequality).
Số thao tác đổi chỗ liền kề tối thiểu để biến một hoán vị thành hoán vị khác chính là số nghịch thế (inversions) của hoán vị kết hợp.
Ta cần xây dựng hoán vị sao cho , rồi đếm số nghịch thế của .
Thuật toán
Tính thứ hạng: Sắp xếp và theo giá trị. Gán = thứ hạng của trong dãy đã sắp xếp (tương tự cho ).
Xây dựng hoán vị: Tạo hoán vị với cho mọi .
Đếm nghịch thế: Dùng Binary Indexed Tree (BIT) / Fenwick Tree:
- Duyệt từ phải sang trái.
- Với mỗi , truy vấn tổng tiền tố trên BIT để đếm số phần tử nhỏ hơn đã xuất hiện (ở bên phải).
- Cập nhật BIT tại vị trí .
- Tổng các truy vấn chính là số nghịch thế.
Modulo: Lấy kết quả modulo .
Độ phức tạp
- Thời gian: — sắp xếp và BIT
- Bộ nhớ:
https://oj.chuyentin.pro/problem/matchstk/editorial
Bình luận