题意：

很基础的模板题，但是要封装一个告诉的St表模板类出来，实测效率不低。

代码：

// 决定写一个ST表的类，维护区间最小值 #include <iostream> #include <vector> #include <stdio.h> using namespace std; template <class Type> class StList { private: bool is_init; int st_size; vector <Type> v; vector <int> log2_floor; // log2_floor[x]表示：(1<<log2_floor[x]) <= x 的最大整数值 log2_floor[x] vector < vector<Type> > st; // st[i][j]: min[ v[i] ... v[i+(1<<j)] ) // len = 1<<j void getStSize(); Type min(const Type& l, const Type& r); public: StList(); ~StList(); void init(); int size(); void push_back(Type x); Type getMin(int l, int r); }; template <class Type> void StList<Type>::getStSize() { st_size = 0; while ((1 << st_size) < v.size()) { st_size++; } } template <class Type> Type StList<Type>::min(const Type& l, const Type& r) { return l < r ? l : r; } template <class Type> StList<Type>::StList() { is_init = true; st_size = 0; v.clear(); st.clear(); log2_floor.clear(); } template <class Type> StList<Type>::~StList() { v.clear(); st.clear(); log2_floor.clear(); } template <class Type> void StList<Type>::init() { getStSize(); st.clear(); vector <Type> unit(st_size + 1); for (int i = 0; i < size(); i++) { // init st[i][0] st.push_back(unit); log2_floor.push_back(-1); ; st[i][0] = v[i]; } for (int i = 1; i < size(); i++) { // init log2_floor; log2_floor[i] = log2_floor[i / 2] + 1; } for (int j = 1; j <= st_size; j++){ for (int i = 0; i < st.size(); i++) { if (i + (1 << (j - 1)) >= st.size()) { break; } st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); } } is_init = true; } template <class Type> int StList<Type>::size() { return v.size(); } template <class Type> void StList<Type>::push_back(Type x) { is_init = false; v.push_back(x); } template <class Type> Type StList<Type>::getMin(int l, int r) { if (is_init == false) { init(); } if (l > r || l < 0 || r >= v.size()) { return Type(); } int len = (r - l + 1); int mov = log2_floor[len]; return min(st[l][mov], st[r - (1 << mov) + 1][mov]); } int main() { StList<int> ans; int n, m; while (cin >> n) { for (int i = 0; i < n; i++) { int temp; scanf("%d", &temp); ans.push_back(temp); } cin >> m; while (m--) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", ans.getMin(l - 1, r - 1)); } } }