#include <stdio.h> #include <math.h> #include <malloc.h> #define N 100000+10 int dp[N][17]; int a[N]; int min(int a,int b){ int t; if(a > b){ t = a;a = b;b =t; } return a; } void st(int a[N],int n){ int i,j,m; for(i = 1;i<=n;i++) dp[i][0] = a[i]; m = (int)(log((double)(n))/log(2.0)); for(j = 1;j<=m;j++){ for(i =1;i+(1<<j)-1<=n;i++) dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } return; } int find(int l,int r){ int k = (int)(log((double)(r-l+1))/log(2.0)); printf("%d\n",min(dp[l][k],dp[r-(1<<k)+1][k])); return 0; } main(){ int n,i,m,x,y,t; scanf("%d",&n); for(i = 1; i<=n; i++) scanf("%d",a+i); st(a,n); scanf("%d",&m); while(m > 0){ scanf("%d%d",&x,&y); if(y < x){ t =x;x=y;y=t; } find(x,y); m--; } return 0; } |
Double click to view unformatted code.