## Dynamic Range Minimum Test

View as PDF

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: , the number of elements in the array, and , the number of operations to perform.

The next lines each contain one non-negative integer less than . Specifically, line number will contain element of the array. Note that the array has zero-based indexing.

The following lines contain one operation each. Each operation is either of the form M i x, indicating that element number is to be changed to , or the form Q i j indicating that your program is to find the minimum value of the elements in the index range (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