[Solution] Final Sum CodeChef Solution | Solution CodeChef

Problem

Chef has an array $A$ of length $N$. In one operation, Chef can:

• 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$.

Chef performed $Q$ such operations where the $i^{th}$ operation was performed on the subarray $[L_i, R_i]$.

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 Format

• 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$.

Output Format

For each test case, output the final sum of the array after performing all the $Q$ operations.

Explanation:

Test case $1$: 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]$.

The sum of final array is $2+3+6+2+3 = 16$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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]$.

The sum of final array is $6$.