POJ3264Balanced Lineup（最基础的线段树）

採用一维数组建树。

（由于一维数组建的是全然二叉树，时间上比用孩子节点指针建树慢。只是基本能够忽略=-=）

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int INF = 0xffffff0;

int minV=INF;

int maxV=-INF;

struct Node

{

    int L,R;

    int minV,maxV;

    int Mid()

    {

        return (L+R)/2;

    }

};

Node tree[800010];

void BuildTree(int root,int L,int R)

{

    tree[root].L=L;

    tree[root].R=R;

    tree[root].maxV=-INF;

    tree[root].minV=INF;

    if(L!=R)

    {

        BuildTree(2*root+1,L,(L+R)/2);

        BuildTree(2*root+2,1+(L+R)/2,R);

    }

}

void Insert(int root, int i,int v)

{

    if(tree[root].L==tree[root].R)

    {

        tree[root].maxV=tree[root].minV=v;

        return;

    }

    tree[root].minV=min(tree[root].minV,v);

    tree[root].maxV=max(tree[root].maxV,v);

    if(i<=tree[root].Mid())

    {

        Insert(2*root+1,i,v);

    }

    else

    {

        Insert(2*root+2,i,v);

    }

}

void Query(int root,int s,int e)

{

    if(tree[root].minV>=minV&&tree[root].maxV<=maxV)

    {

        return;

    }

    if(tree[root].L==s&&tree[root].R==e)

    {

        minV=min(tree[root].minV,minV);

        maxV=max(tree[root].maxV,maxV);

        return;

    }

    if(e<=tree[root].Mid())

    {

        Query(1+root*2,s,e);

    }

    else if(s>tree[root].Mid())

    {

        Query(2+root*2,s,e);

    }

    else

    {

        Query(2*root+1,s,tree[root].Mid());

        Query(2*root+2,tree[root].Mid()+1,e);

    }

}

int main()

{

    int n,q,h;

    int i;

    //freopen("d:\\test.txt","r",stdin);

    scanf("%d%d",&n,&q);

    BuildTree(0,1,n);

    for( i= 1; i <= n; i++ )

    {

        scanf("%d",&h);

        Insert(0,i,h);

    }

    for( i= 0; i < q; i++ )

    {

        int s,e;

        scanf("%d%d", &s,&e);

        minV= INF;

        maxV= -INF;

        Query(0,s,e);

        printf("%d\n",maxV-minV);

    }

    return 0;

}