== include(page="template/taskheader" task_id="undo2") ==
$XORin$ este nemulţumit de problemele primite în prima zi de concurs de la $Olimpiada Naţională de Informatică$ şi decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din şiruri de numere. Din când în când el trebuie să adauge sau să şteargă elemente din şir. Câteodată el decide să readauge dintre elemente şterse anterior. Fie şirul de numere $a$ = (a ~1~ , a ~2~ , ... ,a ~N~ ) şi $N$ numărul de elemente din şir după fiecare operaţie.
Astfel el are de realizat următoarele operaţii pornind de la un şir vid:
* Inserează la sfârşitul şirului o valoare $x$;
* Şterge ultimele $x$ elemente din şir;
* Readaugă la sfârşitul şirului primele $x$ elemente şterse. Dacă, de exemplu, în operaţia anterioară de ştergere a unui număr $y$ de elemente, am şters elementele a ~N-y+1~ , a ~N-y+2~ ,..., a ~N~ , iar acum urmează o operaţie de readăugare a $x$ elemente, vor fi adăugate în ordine elementele a ~N-y+1~ , a ~N-y+2~ ,..., a ~N-y+x~ la sfârşitul şirului.
Din când în când $XORin$ îşi pune următoarea întrebare: de câte ori există valoarea $x$ în şir?
Poveste şi cerinţă...
h2. Date de intrare
Pe prima linie a fişierului $undo2.in$ se va afla $M$ ce reprezintă numărul de operaţii.
Pe următoarele $M$ linii se vor afla operaţiile codificate astfel:
$1 x$ - se inserează elementul $x$ la sfârşitul şirului
$2 y$ - se şterg ultimele $y$ elemente adăugate în şir
$3 z$ - se adaugă înapoi la sfârşitul şirului primele $z$ elemente şterse
$4 t$ - se afişează numărul de elemente cu valoarea $t$ din şir
Fişierul de intrare $undo2.in$ ...
h2. Date de ieşire
Pe fiecare linie a fişierului $undo2.out$ se scriu răspunsurile la întrebările lui $XORin$, fiecare răspuns pe câte o linie.
În fişierul de ieşire $undo2.out$ ...
h2. Restricţii
* Toate numerele din fişierul de intrare sunt cuprinse între $1$ şi $200 000$;
* Pentru $20%$ din teste se garantează $M ≤ 1 000$, pentru alte $40%$ din teste, se garantează că numerele inserate vor fi distincte;
* Între o operaţie de readăugare si operatia anterioară de stergere nu vor exista operatii de inserare.
* Numărul de elemente readăugate nu va fi mai mare decât numărul de elemente şterse la ultima operaţie.
* Între două operaţii de readăugare va exista cel puţin o operaţie de ştergere.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. undo2.in |_. undo2.out |_. Exemplu |
| 16
1 1
1 2
1 3
1 4
4 4
2 2
4 3
3 1
4 4
4 3
1 7
1 7
1 7
4 7
2 2
4 7
| 1
0
0
1
3
1
| Iniţial şirul este vid.
După primele 4 operaţii de inserare şirul este 1, 2, 3, 4.
Operaţia 4 4 va afişa 1.
Operaţia 2 2 va şterge ultimele două elemente şirul devenind 1, 2.
Din cauză că elementul 3 a fost şters, a şaptea operaţie va afişa 0.
Operaţia 3 1 va readăuga la sfârşitul şirului elementul 3.
În urma acestei operaţii şirul devine 1, 2, 3.
Operaţia 4 4 va afişa 0, iar operaţia 4 3 va afişa 1.
ş.a.m.d.
|
table(example). |_. undo2.in |_. undo2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="undo2") ==
