Fişierul intrare/ieşire:rest.in, rest.outSursăSelectie echipe ACM ICPC, UPB 2008
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.7 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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:

  1. modificarea unui element: elementul de pe pozitia x (1 ≤ x ≤ N) ia valoarea y (0 ≤ y < B)
  2. 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.inrest.out
5 10 7
1
3
9
0
7
3
2 2 3
1 3 0
2 3 5
4
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content