Liczba inwersji

Pamięć 16 MB. Czas 1 sek. Permutacja liczb całkowitych od 1 do n jest sekwencją taką, że każda liczba całkowita od 1 do n jest członem sekwencji dokładnie jeden raz. Dwie liczby w permutacji tworzą inwersję, gdy większa jest przed mniejszą. Na przykład, istnieje łącznie 10 inwersji w permutacji 4 2 7 1 5 6 3, utworzonej przez następujące pary: 4-2, 4-1, 4-3, 2-1, 7-1, 7-5, 7 -6, 7-3, 5-3, 6-3. Napisz program, który oblicza liczbę inwersji w danej permutacji.

Wejście

Wartość liczby n(2≤n≤1000000) jest zapisana w pierwszym wierszu standardowego wejścia. Permutacja jest zapisywana w drugim wierszu n liczb rozdzielonych spacjami.

Wyjście

Napisz liczbę inwersji na standardowym wyjściu.

Przykład.
Wejście
7
4 2 7 1 5 6 3
Wyjście
10

Opis:

Do rozwiązania tego zadania należy zastosować algorytm podobny (nawet taki sam) do sortowania przez scalanie. Rekurencyjnie sortowanie dwie podtablice, a następnie scalając podtablice zlicza inwersje.

Rozwiązanie 1:

#include <bits/stdc++.h>
using namespace std;

int ile = 0;

void mer_all(int t[], int l, int v, int r) {
  int Lsize = v - l + 1;
  int Rsize = r - v;

  // tablice pomocnicze
  int *t_tmpL = new int[Lsize];
  int *t_tmpR = new int[Rsize];

  // kopiowanie do tablic pomocnicznych
  for(int i=0; i < Lsize; i++) {
    t_tmpL[i] = t[l + i];
  }
  for( int j = 0; j < Rsize; j++) {
    t_tmpR[j] = t[v + 1 + j];
  }

  // laczenie tablic
  int iL= 0, iR = 0;
  int k;

  for(k=l; iL < Lsize && iR < Rsize; k++){
    if(t_tmpL[iL]<=t_tmpR[iR]){
      t[k] = t_tmpL[iL++];
      ile = ile + (v - k + 1) ;
    } else {
      t[k] = t_tmpR[iR++];
    }
  }
  //Kopiowanie pozosta³ych elementow z tablicy pomocniczej Lewej
  while (iL < Lsize)
    t[k++] = t_tmpL[iL++];
 
  //Kopiowanie pozosta³ych elementow z tablicy pomocniczej Prawej
  while (iR < Rsize)
    t[k++] = t_tmpR[iR++];
  
  // usuniecie tabel pomocniczych
  delete[] t_tmpL;
  delete[] t_tmpR;
}

void merge(int t[], int left, int right) {
  if(right>left){
    int v = (right+left)/2;

    merge(t, left, v);
    merge(t, v+1, right);

    mer_all(t, left, v, right);
  }
}

int inwersja(int t[], int n) {
  merge(t,0,n-1);
  return ile;
}

int main()
{
  int n = 7;
  int t[n]={4,2,7,1,5,6,3};
  cout << inwersja(t, n);
  return 0;
}