Napisałem coś takiego:
https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/KoloStaszica/inwersje_kontratakuja.cpp
Wchodzi na 100 w O(n log n). Pomysł jest taki, ze skoro interesują cię tylko elementy większe na lewo, to sortujesz elementy trzymając strukturę wartosc, idx niemalejąco i teraz, wiesz, że wynikiem są elementy przed tobą(po to sortowaliśmy), które mają < idx niz elementy[i].idx. Elementy przed tobą to te nie sprawdzone jeszcze, więc żeby znać ich sumę to robisz drzewo przedziałowe, gdzie przypisujesz im 1 a jak jakis sprawdzisz to zmieniasz na 0. Więc poprostu proste drzewo przedziałowe punkt-przedział z querry i update. Sortowanie ma O(n log n), operacje na drzewach też O(n log n), więc dostajesz O(n log n)
Widzę, że też oglądasz OKI, super przygotowanie do OIJ i OI-a robią.