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 consideră un vector cu N numere, iniţial egale cu 0, asupra căruia se vor efectua M operaţii astfel:

• UPDATE x l k: Pentru orice i, x <= i <= x + l - 1, valoarea elementului i din vector creşte cu k * (i - x + 1). Practic primul element din interval creşte cu valoarea k, al doilea cu 2 * k şi aşa mai departe până la ultimul element.
• QUERY x y: Se cere să se spună care este suma elementelor de pe intervalul [x, y].

Cerinţă

Dându-se N, M şi cele M operaţii, trebuie să scrieţi un program care să efectueze aceste operaţii într-un mod cât mai eficient şi să scrie în fişierul de ieşire răspunsurile pentru operaţiile de tip QUERY.

Date de intrare

Fişierul de intrare numerex.in va conţine pe prima linie numerele N şi M. Pe următoarele M linii vor fi descrise operaţiile. Fiecare linie care descrie o operaţie începe cu un cod binar (un număr întreg cu valoarea 0 sau 1) şi continuă cu 2 sau 3 numere întregi:

• Un cod 0 va semnifica o operaţie de UPDATE şi va fi urmat de 3 numere x, l şi k (cu semnificaţia din enunţ)
• Un cod 1 va semnifica o operaţie de QUERY şi va fi urmat de 2 numere x şi y (cu semnificaţia din enunţ)

Date de ieşire

În fişierul de ieşire numerex.out se vor scrie pe câte o linie sumele cerute de fiecare operaţie de tip QUERY (sumele se cer în ordinea apariţiei operaţiilor în fişierul de intrare).

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 200 000
• Pentru toate operaţiile de tip UPDATE puteţi considera 1 ≤ k ≤ 100 000
• Pentru toate operaţiile de tip QUERY răspunsul va fi mai mic decât 2⁶⁴

Exemplu

Explicaţie

După prima operaţie de UPDATE vectorul va fi 2 4 6 0, iar suma pe intervalul [2, 4] este egală cu 10.
După a doua operaţie de UPDATE vectorul va fi 2 7 12 9 iar suma pe intervalul [1, 3] este egală cu 21.

Cum se trimit solutii?