# PBinfo #3490 – PermutariAB – Rezolvare C++

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

## Enunț

Se consideră 2 permutări A şi B ale mulţimii {1, 2, ..., N}. Printr-o operaţie se pot selecta două elemente adiacente din B şi să se interschimbe (i.e. swap(B[i], B[i + 1]) pentru 1 ≤ i < N). 

Cerința
Să se determine numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.

Date de intrare
Fişierul de intrare permutariab.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând permutarea A. Pe a treia linie se află de asemenea N numere naturale, separate prin câte un spaţiu, reprezentând permutarea B.

Date de ieșire
Fişierul de ieşire permutariab.out conţine pe prima linie numărul natural X, reprezentând numărul minim de operaţii care trebuiesc efectuate pentru a transforma pe B în A.

Restricții și precizări

1 ≤ N ≤ 100.000
Pentru 70% din teste, 1 ≤ N ≤ 1000

Exemplu 1:
permutariab.in

6
2 1 3 4 5 6
1 3 4 5 6 2
permutariab.out

5
Exemplu 2:
permutariab.in

10
1 5 2 3 4 6 9 10 7 8
3 9 5 1 2 7 8 10 4 6
permutariab.out

17
Explicație
În primul exemplu, se interschimbă 2 cu 6, apoi 2 cu 5, apoi 2 cu 4, apoi 2 cu 3 apoi 2 cu 1.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define Nmax 100010
#define lsb(x) ((x ^ (x - 1)) & x)
#define ll long long
using namespace std;
ifstream fin("permutariab.in");
ofstream fout("permutariab.out");
int N;
int A[Nmax];
int pos[Nmax];
int bit[Nmax];
ll ans;
void update(int pos, int val)
{
    for(; pos <= N; pos += lsb(pos))
        bit[pos] += val;
}
int query(int pos)
{
    int ret = 0;
    for(; pos >= 1; pos -= lsb(pos))
        ret += bit[pos];
    return ret;
}
int main()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
    {
        int x;
        fin >> x;
        pos[x] = i;
    }
    for(int i = 1; i <= N; i++)
    {
        int x;
        fin >> x;
        A[i] = pos[x];
    }
    for(int i = N; i >= 1; i--)
    {
        ans += query(A[i]);
        update(A[i], 1);
    }
    fout << ans << "\n";
    return 0;
}
```

## Resurse

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