学步园

　　以下代码G++超时，C++勉强过，果然是链式的伤不起啊！！！

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

int N, M, rec[200010];

struct Node
{
	int l, r, best;
	Node *lch, *rch;
	Node( int ll, int rr )
	{
		l= ll, r= rr, best= 0, lch= rch= NULL;
	}
	int mid(  )
	{
		return ( l+ r )>> 1;
	}
};

inline int max( int a, int b )
{
	return a> b? a: b;
}

void creat( Node *p )
{
	if( p-> r- p->l> 1 )
	{
		p->lch= new Node( p->l, p->mid() );
		p->rch= new Node( p->mid(), p->r );
		creat( p->lch ), creat( p->rch );
	}
}

int update( Node *p, int pos, int up )
{
	if( p->r- p->l== 1 )
	{
		p->best= up;
		return p->best;
	}
	if( pos>= p->mid() )
	{
		p->best= max( p->best, update( p->rch, pos, up ) );
	}
	else
	{
		p->best= max( p->best, update( p->lch, pos, up ) );
	}
}

int get( Node* p, int l, int r )
{
	if( p->l== l&& p->r== r )
	{
		return p->best;
	}
	if( l>= p->mid() )
	{
		return get( p->rch, l ,r );
	}
	else if( r<= p->mid() )
	{
		return get( p->lch, l, r );
	}
	else
	{
		return max( get( p->lch, l, p->mid() ), get( p->rch, p->mid(), r ) );
	}
}

void _free( Node *p )
{
	if( p->lch )
	{
		_free( p->lch );
	}
	if( p->rch )
	{
		_free( p->rch );
	}
	free( p );
}

void getint( int &num )
{
    char c;
    while( c = getchar(), c< '0'|| c> '9' )  ;
    num = c- '0';
    while( c= getchar(), c>= '0'&& c<= '9' )
    {
        num= num* 10+ c- '0';
    }
}

int main(  )
{
	while( scanf( "%d %d", &N, &M )!= EOF )
	{
		char op[5];
		Node *r= new Node( 1, N+ 1 );
		creat( r );	
		for( int i= 1; i<= N; ++i )
		{
		    int c;
		    getint( c );
			update( r, i, c );
		}	
		for( int i= 1; i<= M; ++i )
		{
			int x, y;
			scanf( "%s", op );
			getint( x ), getint( y );
			if( 'U' == op[0] )
			{
				update( r, x, y );
			}
			else if( 'Q' ==op[0]  )
			{
				printf( "%d\n", get( r, x, y+ 1 ) );
			}
		}
		_free( r );  // 释放所有节点
	}
}