Zadanie inwersje kontratakują 2

Question

Witam, zrobiłem zadanie inwersje kontratakują 2 ale mam za mało punktów, bo zrobiłem je iteracyjnie. Wie ktoś może w jaki sposób użyć w nim drzewa przedziałowego? Żadne sensowne wykorzystanie tej struktury w tym problemie nie przychodzi mi do głowy

Answer 1

Skoro inwersja to taka para indeksów (i, j), ze j < i oraz a_j > a_i  to od razu nasuwa się pomysł, żeby iterować się po indeksie i oraz dodawać do wyniku ilość elementów z przedziału [a_i+1, maks] leżących na lewo od indeksu i

Answer 2

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