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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

There are no comments at the moment.