hdu1753I Hate It（線段樹）

// File Name: hdu1754.cpp   
// Author: bo_jwolf   
// Created Time: 2013年08月16日 星期五 11點27分03秒   
  
#include<vector>   
#include<list>   
#include<map>   
#include<set>   
#include<deque>   
#include<stack>   
#include<bitset>   
#include<algorithm>   
#include<functional>   
#include<numeric>   
#include<utility>   
#include<sstream>   
#include<iostream>   
#include<iomanip>   
#include<cstdio>   
#include<cmath>   
#include<cstdlib>   
#include<cstring>   
#include<ctime>   
  
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;  
}