线段树解法
#include <stdio.h> #include <algorithm> using namespace std; const int maxn = 100010; struct node { int l, r, mid, minn; }tree[maxn<<2]; int a[maxn]; void build(int l, int r, int o) { tree[o].l = l; tree[o].r = r; int m = (l+r) >> 1; tree[o].mid = m; if (l == r) { tree[o].minn = a[l]; return ; } build(l, m, o<<1); build(m+1, r, (o<<1)+1); tree[o].minn = min(tree[o<<1].minn, tree[(o<<1)+1].minn); } int query(int l, int r, int o) { if (tree[o].l == l && tree[o].r == r) return tree[o].minn; if (r <= tree[o].mid) return query(l, r, o<<1); else if (l > tree[o].mid) return query(l, r, (o<<1)+1); else return min(query(l, tree[o].mid, o<<1), query(tree[o].mid+1, r, (o<<1)+1)); } int main() { int t, n, m, l, r; scanf("%d",&t); for (int k = 1; k <= t; k++) { scanf("%d%d",&n, &m); for (int i = 1; i <= n; i++) scanf("%d",&a[i]); build(1, n, 1); printf("Case %d:\n",k); while (m--) { scanf("%d %d",&l, &r); printf("%d\n",query(l, r, 1)); } } return 0; }
Sparse-Table 算法 刘汝佳 训练指南 p197
ST算法：先是预处理部分（构造RMQ数组），DP处理。假设b是所求区间最值的数列，dp[i][j] 表示从i到i+2^j -1中最值(从i开始持续2^j个数)。即dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]},或者dp[i][j]=max{dp[i][j-1],dp[i+2^(j-1)][j-1]}，这个过程的复杂度为：O(n(longn))
接着就是查询最值了，可以通过在O(1)完成查询。就是将查询区间[s,v]，分成两个2^k的区间。
这里只要知道这种算法即可，因为数据量过大，都编译不通过，不过思想算法没有任何问题。
解题代码
#include <stdio.h> #include <algorithm> using namespace std; const int maxn = 100010; int a[maxn]; int d[maxn][maxn]; void rmqinit(int n) { for (int i = 1; i <= n; i++) d[i][0] = a[i]; for (int j = 1; (1<<j) <= n; j++) { for (int i = 1; i+j-1 <= n; i++) d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]); } } int rmq(int l, int r) { int k = 0; while ((1<<(k+1)) <= r-l+1) k++; return min(d[l][k], d[r-(1<<k)+1][k]); } int main() { int t, n, m, l, r; scanf("%d",&t); for (int k = 1; k <= t; k++) { scanf("%d%d",&n, &m); for (int i = 1; i <= n; i++) scanf("%d",&a[i]); rmqinit(n); printf("Case %d:\n",k); while (m--) { scanf("%d %d",&l, &r); printf("%d\n",rmq(l, r)); } } return 0; }
