Suma liczb na lewo mniejszych danej

0

Witam!
Mam taki problem algorytmiczny:
Mam jakiś ciąg liczb, dajmy na to 1 4 5 2 6 7 3. Każdy element występuje raz i mamy tu dokładnie n elementów od 1 do n. Chciałbym dla każdego elementu tego ciągu, idąc po kolei, tzn. najpierw element o wartości 1, potem 2 itd, zobaczyć ile na lewo od tego elementu jest liczb od niego większych. Po takiej operacji skreślam ten element - nadaję mu wartość 0. Mała wizualizacja:
Pierwszy element: 1 na pozycji 1. Ile jest na lewo większych? 0. Zatem wynik zwiększam o 0. Skreślam jedynkę, odtąd tu jest 0.
Drugi element: 2 na pozycji 4. Ile jest na lewo większych? 2. Zatem wynik zwiększam o 2. Skreślam tę dwójkę, odtąd tu jest 0.
Trzeci element: 3 na pozycji 7. Ile jest na lewo większych? 4. Zatem wynik zwiększam o 4. Skreślam tę trójkę, odtąd tu jest 0.

Robię tak dla wszystkich elementów. Chciałbym uzyskać złożoność O(n log n), tzn. pojedynczą operację sprawdzenia ile na lewo większych chciałbym zrobić w czasie log n.
Jak można takie coś zrealizować? Długo myślałem nad jakimś drzewem, chociażby potęgowym, ale tam trzymamy sumę elementów i za nic nie dałem rady tego przekształcić żeby działało jak chcę i wyszukiwało tylko elementy większe od danego.
Pomoże ktoś? Bardzo proszę!

0

Czyli chcesz policzyć liczbę inwersji. Wyczuwam dziwny związek z zadaniem Litery na OI :]

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0