POJ 3264 Balanced Lineup（模板题）【RMQ】

题目大意：

给定一段序列，进行q次询问，输出每次询问区间的最大值与最小值之差。

解题分析：

RMQ模板题，用ST表求解，ST表用了倍增的原理。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 const int M=5e4+10;
 9 int n,q;
10 ll maxsum[M][20],minsum[M][20];
11 void RMQ(){
12     int num=log((double)(n))/log(2.0);
13     for(int j=1;j<=num;j++){
14         for(int i=1;i+(1<<j)-1<=n;i++){
15             maxsum[i][j]=max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);
16             minsum[i][j]=min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);
17         }
18     }
19 }
20 int main(){
21         scanf("%d%d",&n,&q);
22         for(int i=1;i<=n;i++){
23             scanf("%lld",&maxsum[i][0]);
24             minsum[i][0]=maxsum[i][0];
25         }
26         RMQ();
27         while(q--){
28             int x,y;
29             scanf("%d%d",&x,&y);
30             if(x>y)swap(x,y);
31             int k=log((double)(y-x+1))/log(2.0);
32             ll mx=max(maxsum[x][k],maxsum[y-(1<<k)+1][k]);
33             ll mn=min(minsum[x][k],minsum[y-(1<<k)+1][k]);
34             printf("%lld
",mx-mn);
35         }
36     return 0;
37 }

2018-10-19