7326: CodeChef FINALSUM - Final Sum
[Creator : ]
Description
Chef has an array A of length N. In one operation, Chef can:
Determine the final sum of the array after these Q operations.
Note that a subarray is formed by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the array.
- Choose any subarray $[L, R]\ (1 \leq L \leq R \leq N)$;
- Add 1 to $A_L$, subtract 1 from $A_{L+1}$, add 1 to $A_{L+2}$, subtract 1 from $A_{L+3}$ and so on, till $A_R$.
Determine the final sum of the array after these Q operations.
Note that a subarray is formed by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the array.
Input
The first line of input will contain a single integer $T$, denoting the number of test cases.
Each test case consists of multiple lines of input.The first line of each test case contains two integers $N, Q$, number of elements and the number of queries.
The next line contains N space-separated integers $A_1, A_2, \dots A_N$ - denoting the array A.
The next Q lines contains two space-separated integers with $i^{th}$ line containing $L_i, R_i$.
Each test case consists of multiple lines of input.The first line of each test case contains two integers $N, Q$, number of elements and the number of queries.
The next line contains N space-separated integers $A_1, A_2, \dots A_N$ - denoting the array A.
The next Q lines contains two space-separated integers with $i^{th}$ line containing $L_i, R_i$.
Output
For each test case, output the final sum of the array after performing all the $Q$ operations.
Constraints
$1≤T≤1000$
$1 \leq N, Q \leq 3 \cdot 10^5$
$1 \leq A_i \leq 100$
The sum of N over all test cases won't exceed $3 \cdot 10^5$.
The sum of Q over all test cases won't exceed $3 \cdot 10^5$.
$1 \leq N, Q \leq 3 \cdot 10^5$
$1 \leq A_i \leq 100$
The sum of N over all test cases won't exceed $3 \cdot 10^5$.
The sum of Q over all test cases won't exceed $3 \cdot 10^5$.
Sample 1 Input
2
5 3
1 3 4 4 2
1 5
3 4
2 2
1 2
4
1 1
1 1
Sample 1 Output
16
6
Test case 1: The queries are as follows:
Test case 2: The queries are as follows:
- Query 1: The chosen subarray is [1, 3, 4, 4, 2] which changes to [1+1, 3-1, 4+1, 4-1, 2+1] = [2, 2, 5, 3, 3]. Thus, the array becomes [2, 2, 5, 3, 3].
- Query 2: The chosen subarray is [5, 3] which changes to [5+1, 3-1] = [6, 2]. Thus, the array becomes [2, 2, 6, 2, 3].
- Query 3: The chosen subarray is [2] which changes to [2+1] = [3]. Thus, the array becomes [2, 3, 6, 2, 3].
Test case 2: The queries are as follows:
- Query 1: The chosen subarray is [4] which changes to [4+1] = [5]. Thus, the array becomes [5].
- Query 2: The chosen subarray is [5] which changes to [5+1] = [6]. Thus, the array becomes [6].