Opis glavnog rešenja

Jedan od načina rešavanja datog problema je poznat (modifikacija algoritma merge sort). Još jedan način bi mogao da bude i upotreba segmentnih stabala. Rešimo prvo relaksiraniju verziju problema u kojoj niz ne sadrži duplikate.

Prvo ćemo odrediti maksimalnu vrednost \(M\) u ulaznom nizu \(a\), tj. \(M = \max_i a_i\). Nakon toga ćemo pretpostaviti da imamo niz \(b\) veličine \(M + 1\) u koji je popunjen nulama.

Vrednost \(b_i\) je indikator da li odgovarajući element postoji u nizu \(a\). Dakle, ako je \(b_i = 1\), to znači da element \(i\) postoji u početnom nizu \(a\). Ukoliko je \(b_i = 0\), to znači da \(i\) ne postoji u nizu \(a\).

Od niza \(b\) ćemo kreirati segmentno stablo pri unutrašnji čvorovi čuvaju vrednosti koje predstavljaju sume elemenata odgovarajućim segmentima. Iteriramo redom kroz sve elemente niza \(a\). Za svaki element najpre ažuriramo segmentno stablo upisivanjem \(1\) na odgovarajuću poziciju, a zatim izračunamo sume svih unutrašnjih čvorova na koje utiče promena vrednosti lista u koji smo ažurirali. Na ovaj način smo samo naznačili da element postoji u nizu. Nakon toga je potrebno odrediti sumu svih elemenata u nizu \(b\) od pozicije \(x + 1\) do kraja niza (\(x\) je vrednost elementa koji smo dodali u stablo). Šta smo postigli na ovaj način? Svi elementi koji se nalaze desno od elementa \(x\) u nizu \(b\) su sigurno veći od tog elementa. Dodatno, ovi elementi se sigurno nalaze ranije u odnosu na element \(x\) u nizu \(a\) jer redom iteriramo kroz elemente, i one koji su na manjim indeksima ranije dodajemo. Na ovaj način, određujemo broj inverzija broja \(x\) sa svim elementima koji se u originalnom nizu nalaze levo od njega, odnosno imaju manji indeks od njega. Ponavljanjem postupka za sve elemente niza \(a\), dobijamo ukupan broj inverzija.

Rešenje originalnog problema je veoma slično rešenju koje je prikazano. Razlika je u tome što ćemo umesto indikatora koji nam govori da li određena vrednost postoji u početnom nizu imati brojače koji će nam govoriti koliko puta se svaka vrednost pojavila. Na ovaj način možemo odrediti broj inverzija u nizu ukoliko se vrednosti mogu ponavljati.

Složenost kreiranja segmentnog stabla je \(O(M)\), dok je složenost računanja broja inverzija za \(n\) elemenata početnog niza jednaka \(O(n \log M)\).

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int sum(vector<int> &tree, 
        const int i, const int start, const int end, 
        const int l, const int r)
{
    if (start > r || end < l) {
        return 0;
    }

    if (start >= l && end <= r) {
        return tree[i];
    }

    int mid = (start + end) / 2;

    return sum(tree, 2 * i + 1, start,   mid, l, r) 
         + sum(tree, 2 * i + 2, mid + 1, end, l, r);
}

int sum(vector<int> &tree, const int l, const int r)
{
    return sum(tree, 0, 0, r, l, r);
}

void update(vector<int> &tree, 
            const int i, const int start, const int end, 
            const int ind) 
{
    if (start == end) {
        tree[i]++;
        return;
    }

    int mid = (start + end) / 2;

    if (ind <= mid) {
        update(tree, 2 * i + 1, start,   mid, ind);
    } else {
        update(tree, 2 * i + 2, mid + 1, end, ind);
    }

    tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
}

void update(vector<int> &tree, const int n, const int ind)
{
    update(tree, 0, 0, n, ind);
}

int main(void)
{
    int n; cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    const int max = *max_element(arr.begin(), arr.end());

    const int height = ceil(log2(max + 1));
    const int size = 2 * pow(2, height) - 1;

    vector<int> freq(size);

    long long count = 0;
    for (int i = 0; i < n; i++) {
        count += sum(freq, arr[i] + 1, max);
        update(freq, max, arr[i]);
    }
    cout << count << endl;

    return 0;
}