题目大意:给出一段序列,每次查询一段区间,求区间最大值。
ST表:设原序列为A,定义F[i][k]为A[i][2k-1]的最大值。有递归式:F[i][k]=max(F[i][k-1], F[i+2k-1][k-1])。设置F时,外层循环k,内部循环i。查询时,令k为2^k不超过r-l+1的最大k,返回max(F[l][i], F[r-i+1][i])(利用幂等操作)即可。
注意OffOne错误(看代码中的注释)。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_N = 100010, MAX_K = 17; struct ST { private: int F[MAX_N][MAX_K]; public: int A[MAX_N]; int N; void SetF() { for (int i = 0; i < N; i++) F[i][0] = A[i]; for (int k = 1; (1 << k) <= N; k++) for (int i = 0; i + (1 << k) - 1 < N; i++)//F[i][k]管理的是A[i, i+2^k-1],别忘了后面有-1 F[i][k] = max(F[i][k - 1], F[i + (1 << (k - 1))][k - 1]);//子问题只与i, k-1有关,与无关,故<<后k都要-1. } int Query(int l, int r) { int i; for (i = 0; (1 << (i + 1)) <= r - l + 1; i++);//2^k不超过r-l+1,所以<<后面i要+1. return max(F[l][i], F[r - (1 << i) + 1][i]);//看F定义,(1<<i)后有 +1. } }g; int main() { #ifdef _DEBUG freopen("c:\noi\source\input.txt", "r", stdin); #endif int queryCnt; scanf("%d%d", &g.N, &queryCnt); for (int i = 0; i < g.N; i++) scanf("%d", g.A + i); g.SetF(); while (queryCnt--) { int l, r; scanf("%d%d", &l, &r); printf("%d ", g.Query(l - 1, r - 1)); } return 0; }