Fişierul intrare/ieşire:permutare5.in, permutare5.outSursăad-hoc
AutorBogdan PopAdăugată deAlexPop28Pop Alex-Nicolae AlexPop28
Timp execuţie pe test4 secLimită de memorie512000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Permutare5

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 = (p0, p1, ..., pi, pi + 1, ..., pN - 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 (p0, p1, ..., pi + 1, pi, ..., pN - 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.

Date de intrare

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.

Date de ieşire

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.

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.

Exemple

permutare5.inpermutare5.out
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

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).

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ă).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?