1 #include <stdio.h> 2 #include <string.h> 3 const int N = 100; 4 int a[N]; 5 int dp[N][33]; 6 inline int min(const int &a, const int &b) 7 { 8     return a < b ? a : b; 9 }10 11 /*12 dp[i][j] 表示以i开头的，长度为2^j的区间中的最小值13 很明显dp[i][0] = a[i];14 且转移方程为 dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1)][j-1]); 将区间分为2个2^(j-1)的小区间15 */16 void RMQ_init(int n)17 {18     int i,j;19     for(i=1; i<=n; ++i) dp[i][0] = a[i];20     for(j=1; (1<<j)<=n; ++j)21         for(i=0; i+(1<<j)-1<=n; ++i)22             dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);//将区间分为2个2^(j-1)的小区间，dp的思想23 }24 25 //令2^k <= R-L+1, 则以L开头，以R结尾的长度为2^k的区间合起来，就覆盖了区间[L,R]26 //2^k <= R-L+1, 则2^k的长度为区间[L,R]的半数以上，所以以L开头，以R结尾的长度为2^k的区间能够覆盖区间[L,R]27 int RMQ(int L, int R)28 {29     int k = 0;30     while(1<<(k+1) <= R-L+1) k++;31     return min(dp[L][k], dp[R-(1<<k)+1][k]);32 }33 int main()34 {35     int n ,i,L,R;36     scanf("%d",&n);37     for(i=1; i<=n; ++i)38         scanf("%d",&a[i]);39     RMQ_init(n);40     while(scanf("%d%d",&L,&R)!=EOF)41     {42         printf("%d\n",RMQ(L,R));43     }44     return 0;45 }