Inv
Soluţie 1
Problema se poate rezolva în complexitate O(n*log(n)) şi cu ajutorul unei structuri de date tip Arbori Indexaţi Binar, sau Arbori de Intervale. În primul pas vom normaliza şirul din input, adică vom asocia fiecărui număr din şir un număr între 1 şi n astfel încât ordinea relativă a elementelor să rămână neschimbată. Normalizarea se face printr-o sortare a şirului iniţial dacă avem elemente care nu sunt egale sortăm crescător după valoarea lor iar dacă sunt egale sortăm crescator dupa indicele din şirul original.
După ce am obţinut şirul normalizat, îl parcurgem de la stânga la dreapta şi pentru fiecare element: interogăm câte elemente cu indice strict mai mari ca el am introdus în arbore( din acest motiv daca avem valori egale trebuie sa le avem in ordinea crescatoare a pozitiilor pentru ca altfel vom numara si elemenetele cu valoare egala cu cel actual introduse in structura de date) , incrementăm soluţia cu acest număr, după care introducem şi elementul actual în arbore.
Soluţie 2
Întrucât structurile de date menţionate anterior depăşesc nivelul clasei a 10-a, vom prezenta o soluţie ce se bazează pe tehnica divide et impera. La fiecare pas vom împărţi şirul în 2 părţi şi vom aplica algoritmul Merge Sort cu o mică modificare. Când interclasăm cele două bucăţi, reţinem şi bucata în care erau elementele (dacă erau în stânga sau în dreapta). Astfel, pentru fiecare element din partea stângă vom adăuga la soluţie câte elemente din dreapta se află în faţa lui după interclasare, lucru care se poate realiza în timp liniar. Cum adâncimea recursiei este logN, complexitatea finală este O(N logN).
