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 efectua M operatii astfel:

• UPDATE x l k: Pentru orice i, x <= i <= x + l - 1, valoarea elementului i din vector creste cu k * (i - x + 1). Practic primul element din interval creste cu valoay = x + l - 1;rea 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].

Cerinta

Dandu-se N si M si cele M operatii, trebuie sa scrieti un program care sa efectueze aceste operatii intr-un mod cat mai eficient si sa scrie in fisierul de iesire raspunsurile pentru operatiile de tip QUERY.

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, l 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
• Pentru toate operatiile de tip UPDATE puteti considera 1 ≤ k ≤ 100 000
• Pentru toate operatiile de tip QUERY raspunsul va fi mai mic decat 2⁶⁴

Exemplu

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.

Cum se trimit solutii?