9度Oj 1544 数字序列区间最小值

九度Oj 1544 数字序列区间最小值

#include<iostream>#include<stdio.h>#include<cstring>#include<math.h>#include<vector>using namespace std;//vector<int> int A[100006];int min(int a,int b){return a<b?a:b;}int num,d[100202][300];void rmqinit(){int n=num;int i;memset(d,1,sizeof(d));for(i=0;i<n;i++)d[i][0]=A[i];for(int j=1;(1<<j)<=n;j++)for(i=0;i+(1<<j)-1<n;i++){d[i][j]=min(d[i][j-1],d[i+(1<<j-1)][j-1]);}}int rmq(int L,int R){int k=0;while(1<<(k+1)<=R-L+1) k++;return min(d[L][k],d[R-(1<<k)+1][k]);}int main(){int L,R,T;while(scanf("%d",&num)!=EOF){for(int i=0;i<num;i++){scanf("%d",&A[i]);//A.push_back(temp);//printf("%d\n",A[i]);}cin>>T;rmqinit();while(T--){scanf("%d%d",&L,&R);printf("%d\n",rmq(L-1,R-1));}}return 0;}