8636: DSL_2_A : Range Minimum Query (RMQ)
[Creator : ]
Description
Write a program which manipulates a sequence A = {$a_0,a_1,...,a_{n−1}$} with the following operations:
- find(s,t): report the minimum element in $a_s,a_{s+1},...,a_t$.
- update(i,x): change $a_i$ to x.
Note that the initial values of $a_i\ (i=0,1,...,n−1)$ are $2^{31}-1$.
Input
In the first line, n (the number of elements in A) and q (the number of queries) are given.
Then, q queries are given where com represents the type of queries. '0' denotes update($x_i,y_i$) and '1' denotes find($x_i,y_i$).
Output
For each find operation, print the minimum element.
Constraints
$1≤n≤100,000$
$1≤q≤100,000$
If com$_i$ is 0, then $0≤x_i<n, 0≤y_i<2^{31}−1$.
If com$_i$ is 1, then $0≤x_i<n, 0≤y_i<n$.
$1≤q≤100,000$
If com$_i$ is 0, then $0≤x_i<n, 0≤y_i<2^{31}−1$.
If com$_i$ is 1, then $0≤x_i<n, 0≤y_i<n$.
Sample 1 Input
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2
Sample 1 Output
1
2
Sample 2 Input
1 3
1 0 0
0 0 5
1 0 0
Sample 2 Output
2147483647
5