·离线快速区间求最值,O(nlogn)预处理,O(1)查询。
·dp[i][j]表示第i位带i+2^j-1位的区间最大值或区间最小值。
·预处理的转移方程为 dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]; 将区间一分为二。
·查询的时候:l-r区间查询,去len=r-l+1;求的2^k<=len,用k把区间分为l到l+(1<<k)-1和r-(1<<k)+1到r的两个相交叉的部分来求解。
#include <bits/stdc++.h> using namespace std; const int maxn = 10010; int data[maxn]; int max_data[maxn][20],min_data[maxn][20]; int n; void RMQ_init() { for(int i=0;i<=n;i++) max_data[i][0]=min_data[i][0]=data[i]; for(int j=1;(1<<j)<=n;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ max_data[i][j]=max(max_data[i][j-1],max_data[i+(1<<(j-1))][j-1]); min_data[i][j]=min(min_data[i][j-1],min_data[i+(1<<(j-1))][j-1]); } } } int rmq(int l,int r) { int k=0; while((1<<(k+1))<=r-l+1)k++; int ret = max(max_data[l][k],max_data[r-(1<<k)+1][k]); return ret; } int main(){ cin>>n;//数据个数 for(int i=1;i<=n;i++){scanf("%d",&data[i]);} RMQ_init(); int l,r;//查询区间 cin>>l>>r; cout<<rmq(l,r)<<endl; return 0; }