這是kuangbin的RMQ，一維的，代碼很簡潔，附上：

//kuangbin templet(查詢最大值) 一維 //若想查最小，看提示更改 const int MAXN= 50000 + 9 ; int dp[MAXN][20];//第二維是范圍，即2^20約等于100萬 //PS 如果同時要求最大最小，要多開一個dp2[][]來存最小 int mm[MAXN];//mm是間接存的數組

//b[]才是數據，并且b從1開始 void initRMQ(int n,int b[]) {mm[0]=-1;for (int i=1;i<=n;i++){mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];dp[i][0]=b[i];}for (int j=1;j<=mm[n];j++)for (int i=1;i+(1<<j)-1<=n;i++)dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);//PS 若最小 max 改為 min } int RMQ(int x,int y) {int k=mm[y-x+1];return max(dp[x][k],dp[y-(1<<k)+1][k]);//PS 若最小 max 改為 min }

?這是一個很好的測RMQ的題：http://poj.org/problem?id=3264

附上代碼，initRMQ2和RMQ2是初始化最小，和查詢最小的函數。

#include <stdio.h> #include <iostream> using namespace std;const int INF=0x3f3f3f3f; typedef long long ll; #define PI(A) printf("%d\n",A) #define SI(N) scanf("%d",&(N)) #define SII(N,M) scanf("%d%d",&(N),&(M)) #define cle(a,val) memset(a,(val),sizeof(a)) #define rep(i,b) for(int i=0;i<(b);i++) #define Rep(i,a,b) for(int i=(a);i<=(b);i++) #define reRep(i,a,b) for(int i=(a);i>=(b);i--) const double EPS= 1e-9 ;/* / C o d i n g S p a c e / *///kuangbin templet(查詢最大值) 一維 //若想查最小，看提示更改 const int MAXN= 50000 + 9 ; int dp[MAXN][20];//第二維是范圍，即2^20約等于100萬 int dp2[MAXN][20]; int mm[MAXN];void initRMQ(int n,int b[]) {mm[0]=-1;for (int i=1;i<=n;i++){mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];dp[i][0]=b[i];}for (int j=1;j<=mm[n];j++)for (int i=1;i+(1<<j)-1<=n;i++)dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);//PS 若最小 max 改為 min } int RMQ(int x,int y) {int k=mm[y-x+1];return max(dp[x][k],dp[y-(1<<k)+1][k]);//PS 若最小 max 改為 min } void initRMQ2(int n,int b[]) {mm[0]=-1;for (int i=1;i<=n;i++){mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];dp2[i][0]=b[i];}for (int j=1;j<=mm[n];j++)for (int i=1;i+(1<<j)-1<=n;i++)dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);//PS 若最小 max 改為 min } int RMQ2(int x,int y) {int k=mm[y-x+1];return min(dp2[x][k],dp2[y-(1<<k)+1][k]);//PS 若最小 max 改為 min } int N,Q; int input[MAXN]; int main() {while(~SII(N,Q)){Rep(i,1,N) SI(input[i]);initRMQ(N,input);initRMQ2(N,input);rep(i,Q){int a,b;SII(a,b);printf("%d\n",RMQ(a,b)-RMQ2(a,b));}}return 0; }

?

轉載于:https://www.cnblogs.com/s1124yy/p/5688226.html

總結

以上是生活随笔為你收集整理的kuangbin RMQ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。