Mock CCO '18 Contest 3 Problem 4 - Roger Solves A Classic Rage Tree Problem

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.3s
Java 0.6s
Memory limit: 64M

Problem type

Roger is training for CCO and has decided to practice implementing rage trees. He decides to solve a classic problem that is solvable with rage trees.

Given an array with N integers and Q subarray queries, compute the range of each subarray.

Constraints

1 \le N \le 5 \cdot 10^4

1 \le Q \le 2 \cdot 10^5

1 \le a_i \le b_i \le N

a_i, b_i \in \mathbb{C}

The elements of the array are positive integers up to a million.

Input Specification

The first line contains two integers, N and Q.

Each of the next N lines contains a single integer. These N lines constitute the values of the array in order.

Each of the next Q lines contains two integers, a_i and b_i, indicating a 1-indexed query.

Output Specification

For each query, print on a separate line the range of the subarray with leftmost index a_i and rightmost index b_i.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0

Comments