纯RMQ问题
#include<cstdio> #include<iostream> using namespace std; #define MAXN 50010 int n,q; int p[MAXN]; int dpmin[MAXN][20],dpmax[MAXN][20],pw[20]; int log(int n) { int cnt=0; while(n) { cnt++; n>>=1; } return cnt-1; } int main() { pw[0]=1; for(int i=1;i<=20;i++) pw[i]=2*pw[i-1]; while(2==scanf("%d%d",&n,&q)) { for(int i=0;i<n;i++) scanf("%d",p+i); for(int i=0;i<n;i++) { dpmin[i][0]=p[i]; dpmax[i][0]=p[i]; } for(int j=1;j<=log(n);j++) for(int i=0;i<n;i++) { if(i+pw[j-1]>=n) continue; dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+pw[j-1]][j-1]); dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+pw[j-1]][j-1]); } for(int i=0;i<q;i++) { int a,b; scanf("%d%d",&a,&b); a--,b--; int j=log(b-a+1); int ansmax,ansmin; ansmax=max(dpmax[a][j],dpmax[b-pw[j]+1][j]); ansmin=min(dpmin[a][j],dpmin[b-pw[j]+1][j]); printf("%d\n",ansmax-ansmin); } } return 0; }