RMQ模板题，用ST算法
//DP预处理//dp[i][j] 表示从下标i开始，长度为2^j的最大值//状态转移方程 dp[i][j] = max{ dp[i][j-1] , dp[i+2^(j-1)][j-1] }//也就是一个长度为2^j的区间，二分为两个2^(j-1)的长度//对于查询[a,b]以内的最大值,先求出区间长度LEN = b-a+1//查询结果为 res = max{dp[a][k] , dp[b-2^k+1][k]} ， 关键是k，是什么，怎么计算//当满足 2^k >= LEN/2 ， 且k最小时，这个k就是我们要的值//k可以用计算公式一步算得 : k = (int) (log((double)(b-a+1))/log(2.0))//另外一个问题，对于构建dp值的时候,dp[i][j]，这个j最大去到多少？//道理是一样的，对于总区间，长度为L，同样是 2^j >= L/2 , 取最小的j就是我们要的值//所以也可以用公式一步计算出来 j = (int) (log((double)L) / log(2.0))#include #include #include #include using namespace std;#define N 50010#define M 20int n,m,a[N],dp[N][M],__dp[N][M];void TEST(){ cout << "最大值" << endl; int K = (int) (log((double)n) / log(2.0)); for(int i=1; i<=n; i++) for(int j=0; j<=K; j++) printf("dp[%d,%d] = %d\n",i,j,dp[i][j]); cout << "最小值" << endl; for(int i=1; i<=n; i++) for(int j=0; j<=K; j++) printf("__dp[%d,%d] = %d\n",i,j,__dp[i][j]);}void ST(){ for(int i=1; i<=n; i++) dp[i][0] = __dp[i][0] = a[i]; int K = (int) (log((double)n) / log(2.0)); for(int j=1; j<=K; j++) for(int i=1; i+(1< <= n; i++) { int k = i+(1<<(j-1)); dp[i][j] = max( dp[i][j-1] , dp[k][j-1] ); __dp[i][j] = min( __dp[i][j-1] , __dp[k][j-1]); }}int RMQ(int x ,int y){ int K = (int) (log((double)(y-x+1)) / log(2.0)); int k = y-(1< > n >> m) { for(int i=1; i<=n ;i++) cin >> a[i]; ST(); //TEST(); while(m--) { int x,y; cin >> x >> y; int res = RMQ(x,y); cout << res << endl; } } return 0;}