Curious Queries

★★★★★

3.8

9 votes

Segment Trees, Advanced Data Structures, Data Structures

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ of length $N$ . You are asked $Q$ queries. Each query is of the form $L,R$ , and the answer is the sum of $A[i]$ for all $i$ such that $0 \leq i \leq L$ and $A[ i ] > A[ R ]$ .

Print an array $B$ of length $Q$ such that $B[i]$ is the answer to the $i^{th}$ query.

Input format

The first line of input contains a single integer $T$ , which denotes the number of test cases.
The first line of each test case contains two integers $N$ and $Q$ , denoting the length of the array $A$ and the number of queries, respectively.
The second line of each test case contains $N$ integers, denoting the array $A$ .
The following $Q$ lines of each test case contains two integers $L,R$ denoting each query.

Output format

For each test case, print an array $B$ of length $Q$ separated by space such that $B[i]$ is the answer to the $i^{th}$ query in a new line.

Constraints

$1 \leq T \leq 10 \\ 1 \leq N, Q \leq 10^5 \\ 1 \leq A[i] \leq 10^5 \\ 0 \leq L, R \lt N$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For test case $1$ :

For the first query, $i=0,1$ satisfy the given conditions. Therefore the sum is $A[ 0 ] + A[ 1 ] = 6 + 7 = 13$ .
For the second query, no value of $i$ satisfies the given conditions. Therefore the sum is $0$ .
Thus, the answer is $[ 13, 0 ]$ .

For test case $2$ :

For the first query, $i=2,3$ satisfy the given conditions. Therefore the sum is $A[ 2 ] + A[ 3 ] = 3 + 4 = 7$ .
For the second query, $i=1,2$ satisfy the given conditions. Therefore the sum is $A[ 1 ] + A[ 2 ] = 2 + 3 = 5$ .
Thus, the answer is $[7,5]$ .