4084 - Dealing with Range Queries

Created by Rubén Alcolea Núñez
Added by ymondelo20 (2018-09-05)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

In this problem we have to perform three types of queries over an array A that can have at most 1 ≤ N 100000 elements. The queries work as follow:

1. set(a, b, x): set the range [a, b] equal to x. 1 ≤ a ≤ b ≤ N and 0 ≤ x ≤ 100000.
2. update(a, b): update the range [a, b] in the following way: A[i] = A[i] + i – a + 1, such that 1 ≤ a ≤ i ≤ b ≤ N. It means that the value at position a increases by 1, the value at position a + 1 increases by 2, and so on.
3. sum(a, b): return the sum of the array elements in the range [a, b], 1 ≤ a ≤ b ≤ N.

Write a program to perform Q queries as it was explained above.
En este problema, tenemos que realizar tres tipos de consultas sobre un arreglo A que puede tener como máximo 100000 elementos. Las consultas funcionan de la siguiente manera:

1. set (a, b, x): hace el rango [a, b] igual a x. 1 ≤ a ≤ b ≤ 100000 y 0 ≤ x ≤ 100000.
2. update(a, b): actualiza el rango [a, b] de la siguiente manera: A [i] = A [i] + i - a + 1, de modo que 1 ≤ a ≤ i ≤ b ≤ 100000. Significa que el valor en la posición a aumenta en 1, el valor en la posición a + 1 aumenta en 2, y así sucesivamente.
3. sum(a, b): devuelve la suma de los elementos del arreglo en el rango [a, b], 1 ≤ a ≤ b ≤ 100000.

Escriba un programa para realizar Q consultas tal como se explicó anteriormente.
In this problem we have to perform three types of queries over an array A that can have at most 1 ≤ N 100000 elements. The queries work as follow:

1. set(a, b, x): set the range [a, b] equal to x. 1 ≤ a ≤ b ≤ N and 0 ≤ x ≤ 100000.
2. update(a, b): update the range [a, b] in the following way: A[i] = A[i] + i – a + 1, such that 1 ≤ a ≤ i ≤ b ≤ N. It means that the value at position a increases by 1, the value at position a + 1 increases by 2, and so on.
3. sum(a, b): return the sum of the array elements in the range [a, b], 1 ≤ a ≤ b ≤ N.

Write a program to perform Q queries as it was explained above.

Input specification

The first line contains two integers: 1 ≤ N ≤ 100000 and 1 ≤ Q ≤ 200000 representing the number of elements in the array A and the number of queries respectively. The second line contains N integers 0 ≤ Ni ≤ 100000, representing the initial values of the array A. The following Q lines have the information of each query, as it was explained above.
La primera línea contiene dos enteros: 1 ≤ N ≤ 100000 y 1 ≤ Q ≤ 200000 que representan el número de elementos en el arreglo A y el número de consultas, respectivamente. La segunda línea contiene N enteros 0 ≤ Ni ≤ 100000, que representan los valores iniciales del arreglo A. Las siguientes Q líneas tienen la información de cada consulta, como se explicó anteriormente.
The first line contains two integers: 1 ≤ N ≤ 100000 and 1 ≤ Q ≤ 200000 representing the number of elements in the array A and the number of queries respectively. The second line contains N integers 0 ≤ Ni ≤ 100000, representing the initial values of the array A. The following Q lines have the information of each query, as it was explained above.

Output specification

For each sum(a, b) query, print the answer in a single line.
Para cada consulta sum (a, b), imprima la respuesta en una sola línea.
The first line contains two integers: 1 ≤ N ≤ 100000 and 1 ≤ Q ≤ 200000 representing the number of elements in the array A and the number of queries respectively. The second line contains N integers 0 ≤ Ni ≤ 100000, representing the initial values of the array A. The following Q lines have the information of each query, as it was explained above.

Sample input

8 5
0 0 0 0 0 0 0 0
2 5 8
1 7 8 8
3 7 7
3 8 8
3 3 8

Sample output

8
8
19

Hint(s)