Banyak Inversi
Hitung pasangan yang urutannya terbalik untuk data yang besar.
Inversi adalah pasangan posisi i < j dengan data[i] > data[j]. Banyaknya inversi mengukur seberapa jauh data dari terurut. Untuk 20000 data, memeriksa semua pasangan berarti sekitar 200 juta pemeriksaan, terlalu lama. Kamu butuh cara yang lebih cerdik.
Masukan
Baris pertama berisi N (1 sampai 20000). Baris kedua berisi N bilangan bulat dari 1 sampai 10^9.
Keluaran
Banyaknya inversi.
Contoh masukan dan keluaran
Contoh 1
Masukan
5 3 1 4 1 5
Keluaran
3
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Modifikasi merge sort. Saat menggabungkan dua bagian yang sudah terurut, setiap kali elemen dari bagian kanan diambil lebih dulu, ia membentuk inversi dengan semua elemen yang tersisa di bagian kiri.
Petunjuk 2
Jumlahkan inversi dari bagian kiri, bagian kanan, dan dari proses penggabungan.