problema/prieteni2

Prieteni2

== include(page="template/taskheader" task_id="prieteni2") ==
 
Moş Crăciun a vrut să facă un experiment anul acesta, aşa că a adunat $n$ oameni şi i-a înşirat într-o linie. Se ştie că în această perioadă a anului se petrec *trei* tipuri de evenimente stranii.
 
* 1 i - omul *$i$* se împrieteneşte (ca prin minune) cu omul *$i + 1$*
* 2 i - omul *$i$* strică prietenia cu omul *$i + 1$* (un comportament neînţeles)
* 3 a b - Moş Crăciun se întreabă care este cel mai lung şir de prieteni din intervalul *$[a, b]$*
 
Moş Crăciun a încercat să îşi răspundă la întrebări, dar bătrâneţea îşi spune cuvântul. În final vă cere vouă să îl ajutaţi.
 
h2. Date de intrare
 
Fişierul de intrare $prieteni2.in$ va conţine pe prima linie numărul *$n$*, iar pe a doua linie numărul *$q$*. Următoarele $q$ linii vor descrie fiecare câte un eveniment.
 
h2. Date de ieşire
 
Fişierul de ieşire $prieteni2.out$ va conţine răspunsurile pentru evenimentele de tip *$3$*, fiecare pe câte o linie.
 
h2. Restricţii
 
* pentru 40% din punctaj $1 ≤ n, q ≤ 3000$
* pentru alte 30% din punctaj $1 ≤ n, q ≤ 30000$
* pentru alte 30% din punctaj $1 ≤ n, q ≤ 200000$
* pentru evenimente de tip 1 se garantează că $1 ≤ i < n$ şi că i nu e prieten cu i + 1
* pentru evenimente de tip 2 se garantează că $1 ≤ i < n$ şi că i e prieten cu i + 1
* pentru evenimente de tip 3 se garantează că $1 ≤ a, b ≤ n$
 
h2. Exemplu
 
table(example). |_. prieteni2.in |_. prieteni2.out |
| 3
11
3 1 3
1 1
3 1 3
3 2 3
1 2
3 1 3
3 1 2
3 2 3
3 2 2
2 1
3 1 3
|1
2
1
3
2
2
1
2|
| 3
4
1 2
3 1 3
2 2
3 2 3
| 2
1
|
 
h2. Explicaţie pentru exemplul 2
 
* 2 se împrieteneşte cu 3
* cel mai lung lanţ dintre 1 şi 3 este 2-3, de lungime 2
* 2 se supără cu 3
* cel mai lung lanţ dintre 2 şi 3 este de lungime 1 (doar 2, sau doar 3).
 
== include(page="template/taskfooter" task_id="prieteni2") ==

public

task: prieteni2