Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | numerex.in, numerex.out | Sursă | Algoritmiada 2011, Runda 3 |
| Autor | Andrei Parvu, Bogdan-Cristian Tataroiu, Tiberiu Savin | Adăugată de |  Savin Tiberiu •devilkind |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
NumereX
Se considera un vector cu N numere, inital egale cu 0, asupra caruia se vor M operatii astfel:
* UPDATE x y k: Pentru orice i, x <= i <= y, valoarea elementului i din vector creste cu k * (i - x + 1). Practic primul element din interval creste cu valoarea k, al doilea cu 2 * k si asa mai departe pana la ultimul element.
* QUERY x y: Se cere sa se spuna care este suma elementelor pe intervalul [x, y].
Date de intrare
Fisierul de intrare numerex.in va contine pe prima linie numerele N si M. Pe urmatoarele M linii vor fi descrise operatiile. Fiecare linie care descrie o operatie incepe cu un cod binar (un numar intreg cu valoarea 0 sau 1) si continua cu 2 sau 3 numere intregi:
* Un cod 0 va semnifica o operatie de UPDATE si va fi urmat de 3 numere x, y si k (cu semnificatia din enunt)
* Un cod 1 va semnifica o operatie de QUERY si va fi urmat de 2 numere x si y (cu semnificatia din enunt)
Date de ieşire
In fisierul de iesire numerex.out se vor scrie pe cate o linie sumele cerute de fiecare operatie de tip QUERY (sumele se cer in ordinea aparitiei operatiilor in fisierul de intrare).
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ M ≤ 200 000
Exemplu
| numerex.in | numerex.out |
|---|---|
| 4 4 0 1 3 2 1 2 4 0 2 4 3 1 1 3 | 10 21 |
Explicaţie
Dupa prima operatie de UPDATE vectorul va fi 2 4 6 0, iar suma pe intervalul [2, 4] este egala cu 10.
Dupa a doua operatie de UPDATE vectorul va fi 2 7 12 9 iar suma pe intervalul [1, 3] este egala cu 21.
