# PBinfo #3206 – nrinversiuni – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j].

Cerința
Să se determine numărul inversiunilor permutării.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând permutarea.

Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând numărul inversiunilor permutării.

Restricții și precizări

1 ≤ n ≤ 100.000

Exemplu:
Intrare

5
4 2 5 1 3
Ieșire

6
Explicație
Cele 6 inversiuni sunt date de perechile de indici (1,2), (1,4), (1,5), (2,4), (3,4), (3,5).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
long long nrInv;
int a[100005], n, b[100005];
void Interclasare(int p, int m, int q) {
    int i, j, k;
    i = p; j = m + 1; k = 0;
    while (i <= m && j <= q)
        if (a[i] <= a[j]) b[++k] = a[i++];
        else {
            nrInv += (m - i + 1);
            b[++k] = a[j++];
        } while (i <= m) b[++k] = a[i++];
    while (j <= q) b[++k] = a[j++];
    j = p;
    for (i = 1; i <= k; i++) a[j++] = b[i];
}
void Schimbare(int i, int j) {
    int temp;
    if (a[i] > a[j]) {
        nrInv++;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
void MergeSort(int p, int q) {
    int m;
    if (q - p <= 1) Schimbare(p, q);
    else {
        m = (p + q) / 2;
        MergeSort(p, m);
        MergeSort(m + 1, q);
        Interclasare(p, m, q);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    MergeSort(1, n);
	cout << nrInv;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3206)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3206/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3206/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)