Fişierul intrare/ieşire:prieteni2.in, prieteni2.outSursăFMI No Stress 10
AutorStefan RaduAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.25 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

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.

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

Exemplu

prieteni2.inprieteni2.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

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).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?