Write a program which manipulates a sequence A = {a0,a1,...,an−1} with the following operations:
Note that the initial values of ai (i=0,1,...,n−1) are 231-1.
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).
For each find operation, print the minimum element.
3 5 0 0 1 0 1 2 0 2 3 1 0 2 1 1 2
1 2
1 3 1 0 0 0 0 5 1 0 0
2147483647 5
带修改的区间最小值查询，线段树模板题。压了压常数，又打榜了。
1 #include <cstdio> 2 3 inline int min(const int &a, const int &b) { 4 return a < b ? a : b; 5 } 6 7 #define siz 10000000 8 9 char buf[siz], *bit = buf; 10 11 inline int nextInt(void) { 12 register int ret = 0; 13 register int neg = false; 14 15 for (; *bit < ‘0‘; ++bit) 16 if (*bit == ‘-‘)neg ^= true; 17 18 for (; *bit >= ‘0‘; ++bit) 19 ret = ret * 10 + *bit - ‘0‘; 20 21 return neg ? -ret : ret; 22 } 23 24 #define inf 2147483647 25 26 int n, m, mini[400005]; 27 28 int find(int t, int l, int r, int x, int y) { 29 if (x <= l && r <= y) 30 return mini[t]; 31 int mid = (l + r) >> 1; 32 if (y <= mid) 33 return find(t << 1, l, mid, x, y); 34 if (x > mid) 35 return find(t << 1 | 1, mid + 1, r, x, y); 36 else 37 return min( 38 find(t << 1, l, mid, x, mid), 39 find(t << 1 | 1, mid + 1, r, mid + 1, y) 40 ); 41 } 42 43 void update(int t, int l, int r, int x, int y) { 44 if (l == r)mini[t] = y; 45 else { 46 int mid = (l + r) >> 1; 47 if (x <= mid) 48 update(t << 1, l, mid, x, y); 49 else 50 update(t << 1 | 1, mid + 1, r, x, y); 51 mini[t] = min(mini[t << 1], mini[t << 1 | 1]); 52 } 53 } 54 55 signed main(void) { 56 fread(buf, 1, siz, stdin); 57 58 n = nextInt(); 59 m = nextInt(); 60 61 for (int i = 0; i <= (n << 2); ++i)mini[i] = inf; 62 63 for (int i = 1; i <= m; ++i) { 64 int c = nextInt(); 65 int x = nextInt(); 66 int y = nextInt(); 67 if (c) // find(x, y) 68 printf("%d\n", find(1, 1, n, x + 1, y + 1)); 69 else // update(x, y) 70 update(1, 1, n, x + 1, y); 71 } 72 73 // system("pause"); 74 }
@Author: YouSiki
AOJ DSL_2_A Range Minimum Query (RMQ)
原文：http://www.cnblogs.com/yousiki/p/6189185.html