PKU 3264經(jīng)典RMQ。給定一個序列，要求找出給定區(qū)間 [l,r] 中的最大值與最小值之差。
這個算法是最近剛接觸的，最初的感覺就是動態(tài)規(guī)劃能用到這個地步，經(jīng)典啊！
1 #include <iostream>
2 #include <math.h>
3
4 #define max(a,b) ((a>b)?a:b)
5 #define min(a,b) (a<b?a:b)
6
7 using namespace std;
8
9 const int maxn=50001;
10 int h[maxn];
11 int mx[maxn][16],mn[maxn][16];
12 int n,q;
13
14 void rmq_init()
15 {
16 int i,j;
17 for(j=1;j<=n;j++) mx[j][0]=mn[j][0]=h[j];
18 int m=floor(log((double)n)/log(2.0));
19 for(i=1;i<=m;i++){
20 for(j=n;j>0;j--){
21 mx[j][i]=mx[j][i-1];
22 if(j+(1<<(i-1))<=n) mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
23 }
24 }
25 for(i=1;i<=m;i++){
26 for(j=n;j>0;j--){
27 mn[j][i]=mn[j][i-1];
28 if(j+(1<<(i-1))<=n) mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);
29 }
30 }
31 }
32
33 int rmq(int l,int r)
34 {
35 int m=floor(log((double)(r-l+1))/log(2.0));
36 int a=max(mx[l][m],mx[r-(1<<m)+1][m]);
37 int b=min(mn[l][m],mn[r-(1<<m)+1][m]);
38 return a-b;
39
40 }
41
42 int main()
43 {
44 int i,l,r;
45 scanf("%d%d",&n,&q);
46 for(i=1;i<=n;i++) scanf("%d",&h[i]);
47 rmq_init();
48 for(i=0;i<q;i++){
49 scanf("%d%d",&l,&r);
50 printf("%d\n",rmq(l,r));
51 }
52 return 1;
53 }
54