== include(page="template/taskheader" task_id="burlane") ==
Poveste și cerință...
Notă: această problemă este similară cu "Holes":https://codeforces.com/contest/13/problem/E.
O clădire are $N + 1$ etaje numerotate de la 0 la $N$ (considerăm că parterul este etajul 0). Pentru colectarea apei de ploaie, de la fiecare etaj $i ≥ 1$ pornește cîte un burlan care coboară pînă la etajul $p[~i~]$, unde $0 ≤ p[~i~] < i$. Un burlan care ajunge la un etaj se deversează în burlanul care pornește de la acel etaj. Astfel, apa de ploaie de la orice etaj ajunge invariabil la parter, trecînd prin unul sau mai multe burlane.
Dorim să procesăm $Q$ operații, care pot fi de două tipuri:
# Turnăm apă în burlanul care pornește de la etajul $x$ ($0 < x ≤ N$).
# Înlocuim burlanul care pornește de la etajul $x$ ($0 < x ≤ N$) cu unul care duce pînă la etajul $y$. În continuare se garantează că $0 ≤ y < x$.
Pentru fiecare operație de tipul 1, aflați prin cîte burlane trece apa pînă ajunge la parter.
h2. Date de intrare
Fișierul de intrare $burlane.in$ ...
Fișierul de intrare $burlane.in$ conține pe prima linie numerele $N$ și $Q$, separate prin spațiu. A doua linie conține valorile inițiale $p[~1~], p[~2~], ..., p[~N~]$, separate prin spații. Următoarele $Q$ linii conțin operațiile sub una dintre formele:
* $1 x$ pentru operații de tipul 1;
* $2 x y$ pentru operații de tipul 2.
h2. Date de ieșire
În fișierul de ieșire $burlane.out$ ...
În fișierul de ieșire $burlane.out$ afișați răspunsurile la operațiile de tipul 1, cîte unul pe linie.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 100.000$
table{width: inherit}.
|_. subtask |_. puncte |_. restricții |
| 1 | 15 | $N, Q ≤ 10.000$ |
| 2 | 15 | Există cel mult 1.000 de operații de tipul 2. |
| 3 | 70 | Fără restricții suplimentare. |
Testele *nu* sînt grupate.
h2. Exemplu
table(example).
table(example).
|_. burlane.in |_. burlane.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 7 6
0 1 0 2 3 4 3
1 6
1 3
1 7
2 3 2
2 6 5
1 6
| 4
1
2
5
|
h3. Explicație
...
Traseele apei sînt:
* 6 → 4 → 2 → 1 → 0;
* 3 → 0;
* 7 → 3 → 0;
* 6 → 5 → 3 → 2 → 1 → 0.
== include(page="template/taskfooter" task_id="burlane") ==
