Dynamic Range Minimum Test

View as PDF

Submit solution

Points: 12
Time limit: 0.15s
Java 0.5s
PyPy 2 2.5s
PyPy 3 2.5s
Python 2 4.0s
Python 3 4.0s
Memory limit: 8M
PyPy 2 128M
PyPy 3 128M
Python 2 64M
Python 3 64M

Problem type

Perform the dynamic range minimum query.

Input Specification

The first line of input will contain two space-separated integers: N (1 \le N \le 100\,000), the number of elements in the array, and M (1 \le M \le 100\,000), the number of operations to perform.

The next N lines each contain one non-negative integer less than 1\,000\,000. Specifically, line number i contains element i - 2 of the array. Note that the array has zero-based indexing.

The following M lines contain one operation each. Each operation is either of the form M i x, indicating that element number i (0 \le i < N) is to be changed to x (0 \le x < 1\,000\,000), or the form Q i j (0 \le i \le j < N) indicating that your program is to find the minimum value of the elements in the index range [i, j] (that is, inclusive) in the current state of the array and print this value to standard output.

Output Specification

One integer, on its own line, for each Q statement: the answer to the query.

Sample Input

5 10
35232
390942
649675
224475
18709
Q 1 3
M 4 475689
Q 2 3
Q 1 3
Q 1 2
Q 3 3
Q 2 3
M 2 645514
M 2 680746
Q 0 4

Sample Output

224475
224475
224475
390942
224475
224475
35232

Comments


  • 3
    maxcruickshanks  commented on May 10, 2021, 1:31 p.m.

    Since the original data were weak, a second batch was added and each are worth 50 marks.