| Fişierul intrare/ieşire: | rest.in, rest.out | Sursă | Selectie echipe ACM ICPC, UPB 2008 |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Rest
Se dau doua numere naturale N si B si un sir de N numere cu valori naturale cuprinse intre 0 si B-1. Pe acest sir se pot efectua doua tipuri de operatii:
- modificarea unui element: elementul de pe pozitia x (1 ≤ x ≤ N) ia valoarea y (0 ≤ y < B)
- interogarea pe un interval: se cere restul la P al numarului format in baza B prin concatenarea elementelor dintre pozitiile x si y (1 ≤ x ≤ y ≤ N).
Cerinta
Pentru fiecare interogare afisati restul cerut.
Date de intrare
Pe prima linie a fisierului rest.in se afla 3 numere naturale N, B si P cu semnificatia din enunt. Pe urmatoarele N linii se afla cate un element al sirului dat. Apoi se afla numarul M, ce reprezinta numarul total de operatii. Pe urmatoarele M linii se afla cate 3 numere: a x y (a este 1 daca operatia este de modificare, 2 daca operatia este de interogare), iar x si y au semnificatia corespunzatoare fiecarei operatii.
Date de iesire
In fisierul rest.out se vor afla raspunsurile la interogari, cate un numar pe linie, in ordinea data.
Restrictii
- 1 ≤ N, M ≤ 250 000
- 2 ≤ B, P ≤ 30 000
- In urma concatenarii, pozitia cea mai semnificativa din numarul obtinut este x, pozitia x+1 este urmatoarea, etc.
Exemplu
| rest.in | rest.out |
|---|---|
| 5 10 7 1 3 9 0 7 3 2 2 3 1 3 0 2 3 5 | 4 0 |
