// File Name: hdu1754.cpp // Author: bo_jwolf // Created Time: 2013年08月16日 星期五 11点27分03秒 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define lson l , mid , rt << 1 #define rson mid + 1 , r , rt << 1 | 1 const int maxn = 200005 ; //int sum[ maxn << 2 ] ; struct node { int Max ; }tree[ maxn << 2 ] ; void PushUp( int rt ) { tree[ rt ].Max = max( tree[ rt << 1 ].Max , tree[ (rt << 1 | 1 ) ].Max ) ; } void build( int l , int r , int rt ) { if( l == r ) { scanf( "%d" , &tree[ rt ].Max ); return ; } int mid = ( l + r ) >> 1 ; build( lson ) ; build( rson ) ; PushUp( rt ) ; } void update( int p , int add , int l , int r , int rt ) { if( l == r ) { tree[ rt ].Max = add ; return ; } int mid = ( l + r ) >> 1 ; if( p <= mid ) update( p , add , lson ) ; else update( p , add , rson ) ; PushUp( rt ) ; } int query( int L , int R , int l , int r , int rt ) { if( L <= l && r <=R ) { return tree[ rt ].Max ; } int mid = ( l + r ) >> 1 ; int ret = 0 ; if( L <= mid ) ret = max( ret , query( L , R , lson ) ) ; if( R > mid ) ret = max( ret , query( L , R , rson ) ); return ret ; } int main() { int T , n , m ; while( scanf( "%d%d" , &n , &m ) != EOF ) { build( 1 , n , 1 ) ; char op[ 10 ] ; while( m-- ) { scanf( "%s" , op ) ; int a , b ; scanf( "%d%d" , &a , &b ) ; if( op[ 0 ] == 'Q' ) printf( "%d\n" , query( a , b , 1 , n , 1 ) ) ; else update( a , b , 1 , n , 1 ) ; } } return 0; }