SPOJ RPLN (模板题)(ST算法)【RMQ】

题目大意：
给你一段序列，进行q次区间查询，每次都输出询问区间内的最小值。

解题分析：

RMQ模板题，下面用在线算法——ST算法求解。不懂ST算法的可以看这篇博客　>>>

 1 #include <cstdio>
 2 #include<cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int M =1e5+10;
 8 int n,q;
 9 int arr[M],mn[M][20];   //表示从第i个数起连续2^j个数中的最小值
10 void RMQ_init(){    //利用倍增原理预处理st表 
11     int num=log((double)n)/log(2.0);
12     for(int j=1;j<=num;j++){
13         for(int i=1;i+(1<<j)-1<=n;i++){
14             mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
15         }
16     }
17 }
18 int RMQ(int l,int r){
19     int k=log((double)(r-l+1))/log(2.0);
20     int ans=min(mn[l][k],mn[r-(1<<k)+1][k]);  //比较[l,l+(1<<k)-1],[r-(1<<k)+1,r]这两个区间的最值 
21     printf("%d
",ans);
22 }
23 int main(){
24     int T,ncase=0;scanf("%d",&T);
25     while(T--){
26         scanf("%d%d",&n,&q);
27         for(int i=1;i<=n;i++){
28             scanf("%d",&arr[i]);
29             mn[i][0]=arr[i];
30         }
31         RMQ_init();
32         printf("Scenario #%d:
",++ncase);
33         while(q--){
34             int l,r;
35             scanf("%d%d",&l,&r);
36             RMQ(l,r);
37         }
38     }
39     return 0;
40 }

2018-10-19