trang chủ / đề bài / matchstk / lời giải

Kệ Thuốc Phép

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
Tác giả: huunguyenhuunguyen

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

  1. 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 a ghép với phần tử nhỏ nhất của b, 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).

  2. 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.

  3. Ta cần xây dựng hoán vị p sao cho p[ranka[i]]=rankb[i], rồi đếm số nghịch thế của p.

Thuật toán

  1. Tính thứ hạng: Sắp xếp a và b theo giá trị. Gán ranka[i] = thứ hạng của a[i] trong dãy a đã sắp xếp (tương tự cho b).

  2. Xây dựng hoán vị: Tạo hoán vị p với p[ranka[i]]=rankb[i] cho mọi i.

  3. Đếm nghịch thế: Dùng Binary Indexed Tree (BIT) / Fenwick Tree:

    • Duyệt p từ phải sang trái.
    • Với mỗi p[i], truy vấn tổng tiền tố [0,p[i]) trên BIT để đếm số phần tử nhỏ hơn p[i] đã xuất hiện (ở bên phải).
    • Cập nhật BIT tại vị trí p[i].
    • Tổng các truy vấn chính là số nghịch thế.
  4. Modulo: Lấy kết quả modulo 99999997.

Độ phức tạp

  • Thời gian: O(NlogN) — sắp xếp và BIT
  • Bộ nhớ: O(N)

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0