经典问题_rmq_st.cpp

一些ACM基本算法的测试源码

#include<iostream>
using namespace std;

#define _compare max
#define SIZE 200001

int rmq[SIZE][20], bit_len[SIZE];
//得到区间[a,b]的最值。如果要得到区间(a,b)的最值，即GetV(a+1,b-1)。  
int GetRmq(int a, int b)
{
    if(a > b)  return 0;
    int k = bit_len[b - a];
    return _compare(rmq[a][k], rmq[b - (1 << k) + 1][k]);    
}
//RMQ的预处理，这里是取区间的最大值(from数组从0开始存储) 
void CreateRmq(int *from, int size)
{
    int i, j;
    bit_len[0] = bit_len[1] = 0;
    for(i = 2; i <= size; i ++)
        bit_len[i] = bit_len[i / 2] + 1;
    for(i = 0; i < size; i ++)
        rmq[i][0] = from[i];
    for(j = 0; j < bit_len[size]; j ++)
        for(i = 0; i + (1 << j) < size; i ++)
            rmq[i][j + 1] = _compare(rmq[i][j], rmq[i + (1 << j)][j]);     
}

int main()
{
    int i, n, a[200002];
    scanf("%d", &n);
    for(i = 0; i < n; i ++)
        scanf("%d", &a[i]);
    CreateRmq(a, n);    
    int a1, a2;
    while(1)
    {
        scanf("%d%d", &a1, &a2);
        printf("%d\n", GetRmq(a1, a2));        
    }
}