prieteni2

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]$*

* 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. 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

2
2
1

2
|

2|
| 3
4
1 2
3 1 3
2 2
3 2 3
| 2
1
|

h3. Explicaţie

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") ==