经典问题_rmq_segment.cpp

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

#include<iostream>
using namespace std;

#define SIZE 200001
#define INF 1000000000

int from[SIZE];//下标从0开始 

struct NODE{
    int left, right;
    int maxvalue;       
}segmentTree[SIZE];

void Create(int k, int l, int r)
{
    segmentTree[k].left = l;
    segmentTree[k].right = r;
    if(r - l > 1)
    {
        int mid = (l + r) / 2;
        Create(2 * k, l, mid);
        Create(2 * k + 1, mid, r); 
        segmentTree[k].maxvalue = max(segmentTree[2 * k].maxvalue, segmentTree[2 * k + 1].maxvalue);    
    }
    else
    {
        segmentTree[k].maxvalue = from[l - 1];    
    }        
    return;    
}
//得到区间[l,r)的最值,l,r是从1开始的。 
int Search(int k, int l, int r)
{
    if(l <= segmentTree[k].left && r >= segmentTree[k].right)
    {
        return  segmentTree[k].maxvalue;          
    }     
    else
    {
        int mid = (segmentTree[k].left + segmentTree[k].right) / 2;
        int lmax = -INF;
        int rmax = -INF;
        if(l < mid)  lmax = max(lmax, Search(2 * k, l, r));
        if(r > mid)  rmax = max(rmax, Search(2 * k + 1, l, r));
        return  max(lmax, rmax);    
    }
}

int main()
{
    int i, n;
    scanf("%d", &n);
    for(i = 0; i < n; i ++)
        scanf("%d", &from[i]);
    Create(1, 1, n);    
    int a1, a2;
    while(1)
    {
        scanf("%d%d", &a1, &a2);
        printf("%d\n", Search(1, a1 + 1, a2 + 2));        
    }    
}