Range Minimum Query (RMQ)
Write a program which manipulates a sequence A = {a0,a1,...,an−1} with the following operations:
- find(s,t): report the mimimum element in as,as+1,...,at.
- update(i,x): change ai to x.
Note that the initial values of ai (i=0,1,...,n−1) are 231-1.
Input
n q
com0 x0 y0
com1 x1 y1
...
comq−1 xq−1 yq−1
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(xi,yi) and '1' denotes find(xi,yi).
Output
For each find operation, print the minimum element.
Constraints
- 1≤n≤100000
- 1≤q≤100000
- If comi is 0, then 0≤xi<n, 0≤yi<231−1.
- If comi is 1, then 0≤xi<n, 0≤yi<n.
Sample Input 1
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2
Sample Output 1
1
2
Sample Input 2
1 3
1 0 0
0 0 5
1 0 0
Sample Output 2
2147483647
5
带修改的区间最小值查询，线段树模板题。压了压常数，又打榜了。
#include <cstdio>
inline int min(const int &a, const int &b) {
return a < b ? a : b;
}
#define siz 10000000
char buf[siz], *bit = buf;
inline int nextInt(void) {
register int ret = ;
register int neg = false;
for (; *bit < ''; ++bit)
if (*bit == '-')neg ^= true;
for (; *bit >= ''; ++bit)
ret = ret * + *bit - '';
return neg ? -ret : ret;
}
#define inf 2147483647
int n, m, mini[];
int find(int t, int l, int r, int x, int y) {
if (x <= l && r <= y)
return mini[t];
int mid = (l + r) >> ;
if (y <= mid)
return find(t << , l, mid, x, y);
if (x > mid)
return find(t << | , mid + , r, x, y);
else
return min(
find(t << , l, mid, x, mid),
find(t << | , mid + , r, mid + , y)
);
}
void update(int t, int l, int r, int x, int y) {
if (l == r)mini[t] = y;
else {
int mid = (l + r) >> ;
if (x <= mid)
update(t << , l, mid, x, y);
else
update(t << | , mid + , r, x, y);
mini[t] = min(mini[t << ], mini[t << | ]);
}
}
signed main(void) {
fread(buf, , siz, stdin);
n = nextInt();
m = nextInt();
for (int i = ; i <= (n << ); ++i)mini[i] = inf;
for (int i = ; i <= m; ++i) {
int c = nextInt();
int x = nextInt();
int y = nextInt();
if (c) // find(x, y)
printf("%d\n", find(, , n, x + , y + ));
else // update(x, y)
update(, , n, x + , y);
}
// system("pause");
}
@Author: YouSiki