Range update, sum query - MarisaOJ: Marisa Online Judge

Range update, sum query

Time limit: 1000 ms
Memory limit: 256 MB
You are given an array A of n integers. There are q queries of either form: - 1lrx: Add x to Al,Al+1,...,Ar. - 2lr: Find the sum Al+Al+1+...+Ar. ### Input - The first line contains 2 integers n,q. - The second line contains n integers Ai. - The next q lines, each line contains either 3 (for type 2) or 4 (for type 1) integers, a query. ### Output - Print the answer for each query of type 2. ### Constraints - 1≤n,q≤105. - 1≤i≤n. - 1≤l≤r≤n. - 0≤|Ai|,|x|≤106. ### Example Input: 53123322241142235 Output: 812