# PBinfo #2725 – aib – Rezolvare C++

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

## Enunț

Aveți la dispoziție un număr natural nenul n și o permutare a = (a[1], a[2], ..., a[n]) a mulțimii {1, 2, ..., n}.

Cerința
Pentru fiecare număr a[i] trebuie să determinați câte numere mai mici decât a[i] se află la stânga sa, adică în secvența a[1], a[2], ..., a[i-1].

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 pentru fiecare i=1..n câte numere mai mici decât a[i] se află la stânga sa.

Restricții și precizări

3 ≤ n ≤ 100.000

Exemplu:
Intrare

7
3 1 6 5 2 7 4
Ieșire

0 0 2 2 1 5 3
Explicație
Sunt 0 numere mai mici decât 3 și aflate la stânga lui 3.
Sunt 0 numere mai mici decât 1 și aflate la stânga lui 1
Sunt 2 numere mai mici decât 6 și aflate la stânga lui 6 (acestea sunt primele două numere din șir, adică 3 și 1)
Restul e clar, da?

## Cod sursă C++

```cpp
/**
Solutie O(n log n) - arbori indexati binar
*/
#include <iostream>
using namespace std;
int aib[100005], n;
void Update(int i)
{
    for ( ; i <= n; i = i + (i & (-i)))
        aib[i]++;
}
int Query(int i)
{
    int s;
    for (s = 0; i > 0; i = i - (i & (-i)))
        s += aib[i];
    return s;
}
int main()
{
    int i, x;
    cin >> n;
    for (i = 1; i <= n; i++)
    {
        cin >> x;
        cout << Query(x - 1) << " ";
        Update(x);
    }
    return 0;
}
```

## Resurse

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