Inversion Count

Se dă un vector $v$ de lungime $n$ ($n \le 200.000$), ce reprezintă o permutare de ordinul $n$. Se cere să se determine numărul de inversiuni din această permutare. O inversiune este o pereche ordonată $(i, j)$, astfel încât $1 \le i \lt j \le n$ și $v[i] > v[j]$.

Exemplu

Soluție

Soluția naivă constă în a alege fiecare două elemente din vector și a testa dacă acestea formează o inversiune. Complexitatea este $O(n^2)$, și nu se încadrează nici pe departe în limitele problemei.

Observația cheie este că fiecare element, împreună cu elementele de la stânga sa, mai mari decât el, formează câte o inversiune. Asta ne duce cu gândul să folosim un arbore de intervale, în care pe fiecare interval $[x, y]$ să menținem numărul de elemente parcurse până acum, cuprinse între $x$ și $y$.

Așadar, la fiecare pas adăugăm la soluție numărul returnat de $\mathrm{query}(v[i] + 1, n)$, iar apoi facem $\mathrm{update}(v[i], 1)$, însemnând că am găsit elementul $v[i]$. Astfel, data viitoare când vom face un $\mathrm{query}$ pe un interval ce îl cuprinde și pe $v[i]$, se va ști că acesta este inclus în intervalul respectiv.

Complexitatea acestei soluții este $O(n \log_2 n)$, deoarece vectorul este parcurs o singură dată, iar la fiecare pas se efectuează câte două operații pe arborele de intervale, fiecare în $O(\log_2 n)$.

int main() {
    int n, i, x;
    long long int sol = 0;
    cin >> n;
    SegmTree tree(n);

    for (i = 1; i <= n; i++) {
        cin >> x;
        sol += tree.query(x + 1, n);
        tree.update(x);
    }

    cout << sol << '\n';
    return 0;
}