首页 > 代码库 > AOJ DSL_2_A Range Minimum Query (RMQ)
AOJ DSL_2_A Range Minimum Query (RMQ)
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 qcom0 x0 y0com1 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 50 0 10 1 20 2 31 0 21 1 2
Sample Output 1
12
Sample Input 2
1 31 0 00 0 51 0 0
Sample Output 2
21474836475
带修改的区间最小值查询，线段树模板题。压了压常数，又打榜了。
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 214748364725 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 else37 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 else50 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)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。