Fișierul intrare/ieșire | shperl.in, shperl.out | Sursă | selectie lot Nerdvana 2022 |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 3 sec | Limită de memorie | 262144 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Shperl
Pentru că lumea are nevoie de mai mulți programatori, un consorțiu a inventat limbajul Shperl. Acesta este atît de simplu, că oricine poate deveni programator, fără ca măcar să meargă la facultate! În Shperl există un singur tip de date, întregul pe N biți, și doar două tipuri de operații:
- 1 X Y: neagă toți biții aflați pe poziții între X și Y inclusiv;
- 2 X Y: raportează numărul de biți 1 aflați pe poziții ı̂ntre X și Y inclusiv.
Consorțiul vă angajează să testați primul compilator de Shperl din lume, verificînd corectitudinea unui șir de Q operații.
Date de intrare
Fișierul de intrare shperl.in conține pe prima linie întregii N și Q, separați prin spațiu. Următoarea linie conține N caractere ’0’ și ’1’, nedespărțite. Următoarele Q linii conțin cı̂te trei întregi T, X și Y care codifică o operație.
Date de ieșire
În fișierul de ieșire shperl.out afișați, pentru fiecare operație de tip 2, în aceeași ordine ca la intrare, cîte o linie cu rezultatul operației.
Restricții
- 3 ≤ N ≤ 300.000
- 1 ≤ Q ≤ 300.000
- 1 ≤ X ≤ Y ≤ N pentru toate operațiile.
puncte | restricții | |
---|---|---|
1 | 10 | N ≤ 10.000, Q ≤ 10.000 |
2 | 30 | N ≤ 100.000, Q ≤ 100.000 |
3 | 20 | N ≤ 150.000, Q ≤ 150.000 |
4 | 20 | N ≤ 250.000, Q ≤ 250.000 |
5 | 20 | Fără restricții suplimentare. |
Exemplu
shperl.in | shperl.out |
---|---|
7 4 1011011 2 3 6 1 2 4 1 4 7 2 3 7 |
3 2 |
Explicație
Pe pozițiile 3-6 avem biții 1101.
După prima modificare numărul devine 1100011.
După a doua modificare numărul devine 1101100.
Pe pozițiile 3-7 avem biții 01100.