i hate it(linle版).cpp

杭电acm解题报告2001---2099.

#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
#define MAXN 200006
typedef struct Interval_Tree
{
    struct Interval_Tree *ChildLeft,*ChildRight;
    int Left,Right;
    int Maxit;
}IntTree,*PIntTree;

int value[MAXN];
/*PIntTree MakeNode()
{
    PIntTree p;
    p = (PIntTree) malloc ( sizeof(IntTree) );
    memset(p,0,sizeof(IntTree));
    return p;
}*/
IntTree mem[3100050];
int nmem;
PIntTree MakeNode()
{
    PIntTree p;
    p = &mem[nmem++];
    memset(p,0,sizeof(IntTree));
    return p;
}
PIntTree CreateTree(int begin,int end)
{
    int mid = ( begin + end ) / 2;
    PIntTree p = NULL;

    p = MakeNode();
    p->Left = begin;
    p->Right = end;
    if( end - begin < 2 )
    {
        p->Maxit = value[begin] > value[end] ? value[begin] : value[end] ;
    }
    else
    {
        p->ChildLeft = CreateTree(begin,mid);
        p->ChildRight = CreateTree(mid,end);
        p->Maxit = p->ChildLeft->Maxit > p->ChildRight->Maxit ? p->ChildLeft->Maxit : p->ChildRight->Maxit;
    }
    return p;
}
void UpdateTree(PIntTree root,int id)
{
    int mid;
    if( root->ChildLeft == NULL && root->ChildRight == NULL )
    {
        root->Maxit = value[root->Left] > value[root->Right] ? value[root->Left] : value[root->Right] ;
    }
    else
    {
        mid = (root->Left + root->Right) / 2;
        if( id <= mid )
        {
            UpdateTree(root->ChildLeft,id);
        }
        if( id>=mid )
        {
            UpdateTree(root->ChildRight,id);
        }
        root->Maxit = root->ChildLeft->Maxit > root->ChildRight->Maxit ? root->ChildLeft->Maxit : root->ChildRight->Maxit;
    }
}
int GetMax(PIntTree root,int begin,int end)
{
    int mid,t,t2 ;
    if( root->Left == begin && root->Right == end )
    {
        return root->Maxit;
    }
    else
    {
        mid = (root->Left + root->Right) / 2;
        if( begin >= mid )
        {
            return GetMax(root->ChildRight,begin,end);            
        }
        else
        {
            if( end <= mid )
                return GetMax(root->ChildLeft,begin,end);
            else
            {
                t = GetMax(root->ChildLeft,begin,mid);
                t2 = GetMax(root->ChildRight,mid,end);
                return t > t2 ? t : t2 ;
            }
        }
    }
}
int main()
{
    int n,m;
    int i,a,b;
    char cmd[10];
    PIntTree root;
    while(scanf("%d%d",&n,&m)!=EOF )
    {
        nmem = 0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&value[i]);
        }
        root = CreateTree(1,n);
        for(;m>0;m--)
        {
            scanf("%s%d%d",cmd,&a,&b);
            if( cmd[0] == 'U' )
            {
                value[a] = b;
                UpdateTree(root,a);
            }
            else
            {
                if( a == b )
                    printf("%d\n",value[a]);
                else
                    printf("%d\n",GetMax(root,a,b));
            }
        }
    }
}