rmq.txt

RMQ问题是指：对于长度为n的数列A

// StandCode for RMQ, return the smallest number in array s[i..j]
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 1000000
int f2[30];
int s[MAXN];
int r[MAXN][22];

void make_f2(int n)
{
    int i;
    for(i=0;i<=n;i++)
        f2[i]=1<<i;
    return;
}

void make_RMQ(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        r[i][0]=s[i];
    for(j=1;j<=log(n)/log(2);j++)
        for(i=1;i<=n;i++)
            r[i][j]=min(r[i][j-1],r[i+f2[j-1]][j-1]);
    return;
}

int RMQ(int i,int j)
{
    int k=int(log(j-i+1)/log(2));
    return(min(r[i][k],r[j-f2[k]+1][k]));
}

int main()
{
    freopen("rmp.in","r",stdin);
    freopen("rmp.out","w",stdout);

    int n,i,start,end;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    make_f2(20);
    make_RMQ(n);
    while(scanf("%d%d",&start,&end)!=EOF)
        printf("%d\n",RMQ(start,end));
    return 0;
}