题目1544：数字序列区间最小值

http://ac.jobdu.com/problem.php?pid=1544

（1）RMQ算法

#include<stdio.h>
 
int A[100099],d[100099][20];
int n,m;
 
int min(int a,int b){
    return a<=b?a:b;
}
 
void RMQ_init(){
    int i,j;
    for(i=1;i<=n;i++)d[i][0]=A[i];
    for(j=1;(1<<j)<=n;j++){
        for(i=1;i+(1<<j)-1<=n;i++){
            d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
        }
    }
}
 
int RMQ_find(int ll,int rr){
    int k=0;
    while((1<<(k+1))<=(rr-ll+1))k++;
    return min(d[ll][k],d[rr-(1<<k)+1][k]);
}
 
int main(){
    while(scanf("%d",&n)!=EOF){
        int i,j;
        for(i=1;i<=n;i++){
            scanf("%d",&A[i]);
        }RMQ_init();
        scanf("%d",&m);
        int ll,rr;
        while(m--){
            scanf("%d%d",&ll,&rr);
            printf("%d
",RMQ_find(ll,rr));
        }
    }
 
    return 0;
}

（2）开个格外的数组B, B[i]表示i ~b[i] 内第i个数字最小

#include<stdio.h>
 
int A[100099];
int B[100099];
 
int main(){
    int n,m;
    while(scanf("%d",&n)!=EOF){
        int i,j;
        for(i=1;i<=n;i++){
            scanf("%d",&A[i]);
        }
        for(i=1;i<=n;i++){
            for(j=i+1;j<=n&&A[i]<=A[j];j++);
            B[i]=j-1;
        }
        scanf("%d",&m);
        int ll,rr;
        while(m--){
            scanf("%d%d",&ll,&rr);
            while(B[ll]<rr){
                ll=B[ll]+1;
            }
            printf("%d
",A[ll]);
        }
    }
 
    return 0;
}

（3）线段树