Hard Data Structures > Segment Tree/Interval Tree

Professor Mahammad just created a large array using his brand-new true random number generator. However, he does not seem satisfied yet, especially after seeing many different numbers. That is why he came up with a new problem for you. He asks you to count the minimum number of moves to make the range of elements equal for each query. Here **move** denotes adding or subtracting 1 from any element in the range. Input: ------ The very first line of the input contains an integer **T (1 <=T <= 5)**, denoting the number of test cases. Each case consists of several lines. The first one contains two integers **N and Q (1 ≤ N, Q ≤ 5*10^4)** denoting the number of elements of the array and the number of queries respectively. The next line will contain **N** integers separated by spaces, denoting the elements of the array. Then there are **Q** lines each containing 2 space separated integers **1 <= l, r <= N** indicating the queries you need to process. **Each number in the input section is positive and not greater than 10^9.** Output: ------- For each test case, print **Q** lines, describing the minimum number of moves to make the range equal. **Note: Queries do not depend on each other. More formally, you are not required to update the elements of the array during queries.** Sample Input ------------ 1 5 5 1 3 2 4 5 1 3 2 2 1 5 4 5 3 5 Sample Output ------------- 2 0 6 1 3 Note: To equalize range [1, 3] we can change all numbers to 2 in (2 - 1) + (3 - 2) + (2 - 2) = 2 moves. To equalize range [2, 2] no moves are needed. To equalize range [3, 5] we can change all numbers to 4 in (4 - 2) + (4 - 4) + (5 - 4) = 3 moves.

Mahmud Allahverdiyev