== include(page="template/taskheader" task_id="secv8") ==
Se consideră un şir $S$, iniţial vid. Asupra acestuia se efectuează patru operaţii:
# $insert(k, e)$: inserează în $S$ elementul $e$ pe poziţia $k$;
# $access(k)$: întoarce elementul de pe poziţia $k$;
# $reverse(i, j)$: schimbă ordinea elementelor din subşirul $S[i..j]$;
# $delete(i, j)$: şterge subşirul $S[i..j]$.
h2. 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.
Poveste şi cerinţă...
h2. 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:
# $I k e$: $insert(k, e)$, unde $e$ este un număr natural cuprins în intervalul $[0, 10^9^]$ iar $k$ un număr natural cuprins în intervalul $[1, n+1]$.
# $A k$: $acces(k)$, unde $1 ≤ k ≤ n$.
# $R i j$: $reverse(i, j)$, unde $1 ≤ i ≤ j ≤ n$.
# $D i j$: $delete(i, j)$, unde $1 ≤ i ≤ j ≤ n$.
Cu $n$ am notat lungimea şirului.
Fişierul de intrare $secv8.in$ ...
h2. 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.
În fişierul de ieşire $secv8.out$ ...
h2. Restricţii şi precizări
h2. Restricţii
* 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{~1~}s{~2~}..s{~k~}..s{~n~}$ în $S’: s{~1~}s{~2~}..{*e*}s{~k~}..s{~n~}$.
* Operaţia $reverse(i, j)$ va transforma şirul $S: s{~1~}..s{~i-1~}{*s{~i~}s{~i+1~}..s{~j-1~}s{~j~}*}s{~j+1~}..s{~n~}$ în $S’: s{~1~}..s{~i-1~}{*s{~j~}s{~j-1~}..s{~i+1~}s{~i~}*}s{~j+1~}..s{~n~}$.
* Operaţia $delete(i, j)$ va transforma şirul $S: s{~1~}..s{~i-1~}{*s{~i~}s{~i+1~}..s{~j-1~}s{~j~}*}s{~j+1~}..s{~n~}$ în $S’: s{~1~}..s{~i-1~}s{~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.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. secv8.in |_. secv8.out |
| 13 1
I 1 1
I 2 2
I 3 3
R 2 3
I 4 4
I 3 5
A 4
R 1 3
D 2 3
A 3
I 2 1
R 1 3
D 3 3
| 2
4
2 1 4
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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$.
...
== include(page="template/taskfooter" task_id="secv8") ==
