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


  • 0
    9o  commented on Sept. 17, 2023, 2:58 p.m.

    why am i getting presentation error: https://dmoj.ca/submission/5779275


    • 1
      Xyene  commented on Sept. 17, 2023, 7:59 p.m.

      The output of your submission does not match the output format of the problem. If you tried the sample case locally, you'd see why.


      • 0
        9o  commented on Sept. 17, 2023, 8:55 p.m.

        but i have tried it in an editor and the sample case works fine


        • 1
          dnialh_  commented on Sept. 19, 2023, 6:04 a.m.

          If your editor is somehow displaying output incorrectly you can also see the output of your program on the first testcase in DMOJ by clicking on the arrow on the left.