3

Squares Sum

Difficulty: HARD
Contributed By
Achint Narang
Avg. time to solve
45 min
Success Rate
55%

Problem Statement

Given an array of ‘N’ integers and ‘q’ queries. The query is defined as below:-

Given two integers ‘l’ and ‘r’ ( ‘l’ >=0 and ‘r’ <= ‘N’) Find the sum of squares of all elements of the array with index in the range ‘l’ and ‘r’ (Inclusive).

Given three integers ‘l’ ,’r’ and ‘x’ ( ‘l’ >=0 and ‘r’ <= ‘N’) .Update the elements of the array by incrementing ‘x’ to all array elements with index in the range ‘l’ and ‘r’.

Given three integers ‘l’ ,’r’ and ‘x’ ( ‘l’ >=0 and ‘r’ <= ‘N’) .Update the elements of the array by setting ‘x’ to all array elements with index in the range ‘l’ and ‘r’.

Input Format :
The first line contains ‘T,’ denoting the number of test cases.

The first line of the test case contains a single integer ‘N’  denoting the size of the ‘arr’ array.

The second line of each test case contains ‘N’ space-separated integers denoting the array ‘arr’.

The third line of each test case contains an integer ‘q’ denoting the number of queries.

The next ‘q’  lines of each test case contain 3 or 4 space-separated integers denoting the following:

1 The first integer denotes the type of query.It can be either ‘0’ , ‘1’ , ‘2’.  ‘0’ denotes the range update query by adding ‘x’ to all array elements within the index range. ‘1’ denotes the range update query by setting ‘x’ to all array elements within the index range. ‘2’ denotes sum of squares type query. 

2 If the query is of ‘0’ and ‘1’ type then second, third and fourth integers in the same line denotes  ‘l’ ,’r’ and ‘x’ denotes the range for which to update the values.

3 If the query is of ‘2’ type then second and third integers in the same line denote ‘l’ and ‘r’  denotes the range for which to calculate the sum of squares.
Output Format :
For each query of type ‘2’  print the sum of squares .in the range of ‘l’ and ‘r’. For update query do not print anything just update the values in an array.
Constraints :
1 <= ’T’ <= 10
1 <= ‘N’ <= 1000
1 <= q <= 1000
1 <= arr[i] <= 1000
1 <= ‘x’ <= 1000

Where ‘i’ varies from 0 to ‘n’ -1  where ‘n’ is the length of the array ‘arr’,q is the number of queries ‘arr[i]’ is the value of the element at index ‘i’. ‘x’ is the number for updating the range. 


Time Limit: 1 sec
Sample Input 1 :
1
5
1 2 3 4 5
5
2 0 2
0 0 2 1
2 0 3
1 0 2 2
2 0 4
Sample Output 1 :
14
45
53
Sample Output Explanation :
The first line has a single integer which means it’s a single test case.
The next line has an integer 5 denoting that there are 5 integers in the array.
Then the 5 space-separated integers in the third line represent the elements in the array.
Then the fourth line has ‘q’ which is the number of queries. In this case, we have 5 queries.

The 5 queries are as follow:-

In first query type = 2   ‘l’ = 0 and ‘r’ = 2
The sum of squares is  arr[0]^2 + arr[1]^2 + arr[2]^2 = 1^2 + 2^2 + 3^2 = 14

In second query type = 0  ‘l’ = 0 and ‘r’ = 2 and ‘x’ = 1.
Incrementing ‘x’ from 0 to 2 in an array. Thus array becomes [ 2,3,4,4,5].

In third query type = 2 ‘l’ = 0 and ‘r’ = 3.
The sum of squares is arr[0]^2 + arr[1]^2 + arr[2]^2 + arr[3]^3 = 2^2 + 3^2 + 4^2 + 4^2 = 45

In fourth query type = 1  ‘l’ = 0 and ‘r’ = 2 and ‘x’ = 2.
Setting ‘x’ from 0 to 2 in an array. Thus array becomes [2,2,2,4,5].

In fifth query type = 2   ‘l’ = 0 and ‘r’ = 4
The sum of squares is arr[0]^2 + arr[1]^2 + arr[2]^2 + arr[3]^3 + arr[3]^2  = 53
Sample Input 2 :
2
5
1 10 5 1 3 
4
0 1 1 10
1 2 2 6
0 1 4 6
2 0 4 
6
6 2 8 3 5 2 
3
0 1 2 2
2 1 1 
2 0 2  
Sample Output 2 :
951
16
152
Reset Code
Full screen
copy-code
Console