Inversiyalar soni

$n$ ta butun sondan iborat massiv berilgan. Uni faqat qo'shni elementlarning o'rnini almashtirish orqali o'sish tartibida saralash kerak. Eng kamida nechta almashtirish kerak?

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta butun son ($|a_i| \le 10^9$).

Bitta son — almashtirishlarning eng kam soni.

Har bir qo'shni almashtirish aynan bitta inversiyani — $i < j$ va $a_i > a_j$ bo'lgan juftlikni — yo'q qiladi, shuning uchun javob inversiyalar soniga teng. Ularni merge sort ichida sanang: ikki saralangan yarmini birlashtirishda o'ng yarmdan element olinsa, chap yarmda qolgan barcha elementlar undan katta — shuncha inversiya qo'shiladi. Bu $O(n \log n)$; pufakcha saralashni simulyatsiya qilish $O(n^2)$.

Teng elementlar inversiya hosil qilmaydi: birlashtirishda tenglarda chap yarmdan oling. Javob $2 \cdot 10^{10}$ gacha yetadi — 64 bitli tur kerak. Ikkinchi misolda javob $6$.

Manba: UVa 10810.