POJ 3264 Balanced Lineup[RMQ入门题]

题目链接：?id=3264

题目大意：n个数，，求区间[ L,R ]的最大最小值之差；

题目分析：

RQM：dp[ i ][ j ], i开始长度为2^j的长度的区间最值；

O（nlog n）的预处理区间值，O（1）的查询；

代码：

//author: ACsorry//result: accept#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<string>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#define INF 1<<29#define SUP 0x80000000#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int N=1000007;int dp[N][20]; //2^20已经10^6的数组了//dp[i][j] 从i开始的2^j长度的区间最值int A[N]; //下标从1开始void rmqInit(int n) //n为数组大小{for(int i=1;i<=n;i++) dp[i][0]=A[i];for(int j=1;(1<<j)<=n;j++){for(int i=1;i+(1<<j)-1<=n;i++){dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);}}}int query(int L,int R) //查询[L,R]区间最值{int m=floor(log(R-L+1.0)/log(2.0));return min(dp[L][m],dp[R-(1<<m)+1][m]);}int dp1[N][20];void rmqInit1(int n) //n为数组大小{for(int i=1;i<=n;i++) dp1[i][0]=A[i];for(int j=1;(1<<j)<=n;j++){for(int i=1;i+(1<<j)-1<=n;i++){dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);}}}int query1(int L,int R) //查询[L,R]区间最值{int m=floor(log(R-L+1.0)/log(2.0));return max(dp1[L][m],dp1[R-(1<<m)+1][m]);}int main(){int n,m;while(scanf("%d%d",&n,&m)==2){for(int i=1;i<=n;i++) scanf("%d",A+i);rmqInit(n);rmqInit1(n);int L,R;//cout<<query(1,6)<<endl;while(m–){scanf("%d%d",&L,&R);printf("%d\n",query1(L,R)-query(L,R));}}return 0;}

//宁愿精彩的活，也不愿平庸一辈子。

偶尔也要现实和虚伪一点，因为不那样做的话，很难混。