Fișierul intrare/ieșire shperl.in, shperl.out Sursă selectie lot Nerdvana 2022
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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 ≤ XYN 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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii