Folklore

Segment Tree Test

Perform the dynamic range minimum query.

Input

The first line of input will contain two space-separated integers: N (1 ≤ N ≤ 100 000), the number of elements in the array, and M (1 ≤ M ≤ 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 ≤ i < N) is to be changed to x (0 ≤ x < 1 000 000), or the form Q i j (0 ≤ ij < 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

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

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 14, 2010
Author: bbi5291

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I checked all my functions but I cannot find any fault in my functions. I've also checked the limits but I am still getting only 20 points. Someone please help

Hello. Excuse the whine. Mostly I'm just curious. My Python solution timed out on the last two cases, whereas my (nearly identical) C solution made them comfortably. Is this intentional? Is this problem purposefully difficult for interpreted languages? Or is it just a hazard of writing in Python?

OTOH maybe I just have a subtle bug somewhere.

it is a hazard to write in python

As far as I can tell, there are no problems that are purposefully difficult for interpreted languages. If the problem setter didn't want you to use Python then they'd just disallow Python submissions. That being said, we usually don't make any special effort to allow languages that are not {C, C++, Pascal} to pass.

Noted. Thanks for the reply.