原题链接:https://www.luogu.com.cn/problem/P1816
题意解读:m个数,n个询问,每次询问计算l~r之间最小值。
解题思路:
典型的RMQ问题,ST表模版题,对于ST表前面已有具体介绍,不多废话,直接上代码
100分代码:
#include <bits/stdc++.h>
using namespace std;const int M = 100005;int a[M], st[M][20]; //s[i][j]表示从i开始,长度为2^j范围的最小值
int m, n;int main()
{cin >> m >> n;for(int i = 1; i <= m; i++) {cin >> a[i];st[i][0] = a[i];}for(int j = 1; j <= log2(m); j++){for(int i = 1; i + (1 << j - 1) - 1 <= m; i++){st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);}}int l, r;while(n--){cin >> l >> r;int len = log2(r - l + 1);cout << min(st[l][len], st[r - (1 << len) + 1][len]) << " ";}return 0;
}