- Time limit: 5.00 s
- Memory limit: 256 MB
Tehtävänäsi on ylläpitää luvun taulukkoa. Aluksi taulukko on täynnä nollia. Taulukkoon tehdään seuraavanlaisia kyselyjä:
- H: laske taulukon yhtenäisen välin polynomihajautusarvo
- R: käännä taulukon yhtenäinen väli ympäri
- A: lisää taulukon yhtenäisellä välillä kaikkiin lukuihin annettu arvo
Lukujonon polynomihajautusarvo on modulo , missä .
Syöte
Syötteen ensimmäisellä rivillä on luvut ja , taulukon koko ja kyselyiden lukumäärä. Seuraavat riviä sisältävät kyselyt. Jokaisella kyselyrivillä on ensin merkki, joka kertoo kyselyn tyypin: S, R tai A. Rivin loppu riippuu kyselytyypistä:
- H: luvut ja , välin alku- ja loppukohdat ()
- R: luvut ja , välin alku- ja loppukohdat ()
- A: luvut ja ja , välin alku- ja loppukohdat, sekä välin jokaiseen alkioon lisättävä luku, ()
Tuloste
Tulosta jokaista H-kyselyä kohti välin polynomihajautusarvo omalle rivilleen.
Rajat
Esimerkki
Syöte:
8 24 R 7 8 R 2 3 A 1 3 66 H 1 5 A 2 4 43 R 1 4 R 5 6 H 3 8 R 4 8 A 1 7 8 H 6 6 R 1 3 A 4 8 91 H 3 7 H 2 3 R 4 8 R 4 8 H 4 4 H 7 8 A 1 6 74 H 1 6 A 6 6 88 A 5 6 13 H 2 4
Tuloste:
1005944205660722526 8148148183 8 1731100457623044023 6296296356 99 19382715972 12342422904188490918 2636793139215058949