== include(page="template/taskheader" task_id="permutare5") ==
Poveste şi cerinţă...
Fie o permutare $P$ de lungime $N$. Considerăm operaţia de interschimbare de valori aflate pe două poziţii consecutive.
Definim o permutare de lungime $N$ ca fiind un şir care conţine toate numerele de la $0$ la $N - 1$ exact odată. Fie o permutare $P = (p{~0~}, p{~1~}, ..., p{~i~}, p{~i + 1~}, ..., p{~N - 1~})$ şi un indice $0 ≤ i < N - 1$. În urma interschimbării valorilor aflate pe poziţiile $i$ şi $i + 1$ din $P$, permutarea $P$ devine $(p{~0~}, p{~1~}, ..., p{~i + 1~}, p{~i~}, ..., p{~N - 1~})$.
Concurentul (adică tu) poate cumpăra astfel de interschimbări. Odată cumpărată, o interschimbare poate fi folosită de oricâte ori. Definim costul lui $P$ ca fiind numărul minim de astfel de interschimbări ce trebuie cumpărate astfel încât permutarea să poată fi sortată folosind doar interschimbările cumpărate, fiecare de oricâte ori.
Comisia (adică noi) schimbă de $Q$ ori permutarea $P$ prin interschimbarea valorilor de pe două poziţii arbitrare, *nu neapărat adiacente*. Odată făcută o schimbare asupra permutării, ea rămâne valabilă în continuare.
Atât pentru permutarea iniţială, cât şi pentru permutarile obţinute după fiecare dintre schimbările comisiei, se cere costul lui $P$.
h2. Date de intrare
Fişierul de intrare $permutare5.in$ ...
Fişierul de intrare $permutare5.in$ conţine, pe primul rând, numărul $N$ de elemente a permutării vizate, şi numărul $Q$ de operaţii.
Pe al doilea rând vor apărea cele $N$ elemente a permutării $P$.
Urmează $Q$ rânduri de forma $a b$, dintre care fiecare reprezintă o interschimbare a elementelor de pe poziţiile $a$ şi $b$.
h2. Date de ieşire
În fişierul de ieşire $permutare5.out$ ...
Fişierul de ieşire $permutare5.out$ va conţine $Q + 1$ rândurile, conţinând costul permutării iniţiale, cât şi a tuturor permutărilor obţinute după fiecare dintre schimbările comisiei, în ordine.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 200.000$
* Pentru 6 puncte, $1 ≤ N ≤ 1.000, 1 ≤ Q ≤ 10$
* Pentru 13 puncte, $2 ≤ N ≤ 100.000, 1 ≤ Q ≤ 100$
* Pentru 46 puncte, $2 ≤ N ≤ 50.000, 1 ≤ Q ≤ 50.000$
* Pentru 22 puncte, $2 ≤ N ≤ 100.000, 1 ≤ Q ≤ 200.000$ şi schimbările făcute de comisie interschimbă doar valori de pe poziţii adiacente. Mai exact, $y = x + 1$ pentru toate schimbarile comisiei.
h2. Exemplu
h2. Exemple
table(example). |_. permutare5.in |_. permutare5.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3 4
0 1 2
0 1
0 1
0 2
1 2
| 0
1
0
2
2 |
| 4 6
0 3 2 1
1 2
1 3
0 2
0 1
1 2
0 2
| 2
2
1
3
3
2
3 |
h2. Explicaţie pentru primul exemplu:
În permutarea iniţială, $(0, 1, 2)$, nu este nevoie de nicio interschimbare pentru a sorta permutarea.
În permutarea de după prima schimbare, $(1, 0, 2)$, este nevoie de cumpărarea interschimbarii $(0, 1)$.
Permutarea de după a doua schimbare este indentică cu cea iniţială.
Penultima permutare este $(2, 0, 1)$ şi este nevoie de cumpărarea transpoziţiilor $(0, 1)$ şi $(1, 2)$.
h3. Explicaţie
Ultima permutare este $(2, 1, 0)$, iar interschimbarile $(0, 1)$ şi $(1, 2)$ rămân ambele necesare *(chiar dacă sunt folosite de mai multe ori, fiecare este cumpărată doar o dată).
...
== include(page="template/taskfooter" task_id="permutare5") ==
== include(page="template/taskfooter" task_id="permutare5") ==
