Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | spiridusi.in, spiridusi.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Cătălin Frâncu | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.3 sec | Limită de memorie | 524288 KB |
| Scorul tău | N/A | Dificultate |
   2.25
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Spiriduși (clasele 9-12)
Spiridușii lui Moș Crăciun tocmai au terminat de asamblat o instalație luminoasă. Ea are n beculețe dispuse în lanț, numerotate de la 1 la n. Acum, spiridușii testează instalația. Mai întîi ei aprind o parte dintre beculețe, apoi fac q operații de două tipuri:
- 1 x: Schimbă starea beculețului x (aprinde beculețul dacă era stins și invers).
- 2 x y: Află cel mai mare număr de beculețe consecutive aprinse între pozițiile x și y inclusiv.
Ajutați-i pe spiriduși să afle răspunsurile la operațiile de tipul 2!
Date de intrare
Fișierul de intrare spiridusi.in conține pe prima linie numerele n și q. Pe următoarea linie apar n caractere 0 sau 1, fără spații, indicînd starea inițială a beculețelor (0 = stins, 1 = aprins). Pe următoarele q linii se află cîte o operație, sub una dintre formele 1 x (cu 1 ≤ x ≤ n) sau 2 x y (cu 1 ≤ x ≤ y ≤ n).
Date de ieșire
În fișierul de ieșire spiridusi.out afișați răspunsul la operațiile de tip 2, cîte unul pe linie.
Restricții
- 1 ≤ n, q ≤ 200.000
- Testele nu sînt grupate.
| subtask | puncte | restricții |
|---|---|---|
| 1 | 30 | n, q ≤ 20.000 |
| 2 | 40 | n q ≤ 60.000 |
| 3 | 30 | Fără restricții suplimentare. |
Exemplu
| spiridusi.in | spiridusi.out |
|---|---|
| 9 4 100110111 2 4 8 2 2 3 1 6 2 4 8 |
2 0 5 |
Explicație
Pe pozițiile 4-8 se află beculețele 11011 și există două beculețe consecutive aprinse.
Pe pozițiile 2-3 se află beculețele 00. Nu există beculețe consecutive aprinse.
După aprinderea beculețului 6, instalația devine 100111111.
Acum pe pozițiile 4-8 există 5 beculețe consecutive aprinse.
