Fişierul intrare/ieşire:	secv8.in, secv8.out	Sursă	Lot Bistrita 2009, Baraj 2
Autor	Marius Stroe	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	2.5 sec	Limită de memorie	67583 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Secv8

Se consideră un şir S, iniţial vid. Asupra acestuia se efectuează patru operaţii:

1. insert(k, e): inserează în S elementul e pe poziţia k;
2. access(k): întoarce elementul de pe poziţia k;
3. reverse(i, j): schimbă ordinea elementelor din subşirul S[i..j];
4. delete(i, j): şterge subşirul S[i..j].

Cerinţă

Se cere să se răspundă la toate operaţiile de tipul 2 şi să se afişeze elementele şirului S după efectuarea tuturor operaţiilor.

Date de intrare

Pe prima linie a fişierului de intrare secv8.in se vor găsi două numere naturale, primul reprezentând numărul operaţiilor din fişier, iar al doilea va fi 1 dacă există operaţia reverse şi 0 dacă nu există. Următoarele linii vor fi de patru tipuri, corespunzătoare fiecărei operaţii:

1. I k e: insert(k, e), unde e este un număr natural cuprins în intervalul [0, 10⁹] iar k un număr natural cuprins în intervalul [1, n+1].
2. A k: acces(k), unde 1 ≤ k ≤ n.
3. R i j: reverse(i, j), unde 1 ≤ i ≤ j ≤ n.
4. D i j: delete(i, j), unde 1 ≤ i ≤ j ≤ n.

Cu n am notat lungimea şirului.

Date de ieşire

În fişierul de ieşire secv8.out se vor tipări pe câte un rând răspunsurile operaţiilor de tipul 2 în ordinea în care apar în fişierul de intrare. Pe ultima linie se va tipări secvenţa S după efectuarea tuturor operaţiilor.

Restricţii şi precizări

• Numărul operaţiilor insert nu va depăşi 250 000.
• Numărul total al operaţiilor nu va depăşi 750 000.
• Operaţia insert(k, e) va transforma şirul S: s₁s₂..s_k..s_n în S’: s₁s₂..es_k..s_n.
• Operaţia reverse(i, j) va transforma şirul S: s₁..s_i-1s_is_i+1..s_j-1s_js_j+1..s_n în S’: s₁..s_i-1s_js_j-1..s_i+1s_is_j+1..s_n.
• Operaţia delete(i, j) va transforma şirul S: s₁..s_i-1s_is_i+1..s_j-1s_js_j+1..s_n în S’: s₁..s_i-1s_j+1..s_n.
• Se garantează că operaţiile 2, 3 şi 4 nu se vor efectua asupra unei secvenţe vide.
• Pentru 15% din teste numărul operaţiilor insert nu va depăşi 35 000 iar numărul total al operaţiilor 100 000. Pentru aceste teste va exista operaţia reverse.
• Pentru încă 25% din teste operaţia reverse nu se va regăsi.

Exemplu

Explicaţie

Şirul S devine succesiv: 1, 1 2, 1 2 3, 1 3 2, 1 3 2 4, 1 3 5 2 4, 5 3 1 2 4, 5 2 4, 5 1 2 4, 2 1 5 4, 2 1 4. Numerele îngroşate sunt răspunsurile operaţiilor de tipul 2.

Cum se trimit solutii?