学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1754

基础线段树，单点替换，区间最值。

code:

#include<cstdio>
#include<algorithm>
using namespace std ;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 200010 ;
int sum[maxn<<2] ;
template <class T>
inline void scan_d(T &ret) {
    char c; ret=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}
void PushUp(int rt){
    sum[rt] = max(sum[rt<<1], sum[rt<<1|1]) ;
}
void build(int l, int r, int rt){
    if(l==r){
        scan_d(sum[rt]) ;
        return ;
    }
    int m = (l + r) >> 1 ;
    build(lson) ;
    build(rson) ;
    PushUp(rt) ;
}
void update(int p, int t, int l, int r, int rt){
    if(l==r){
        sum[rt] = t ;
        return ;
    }
    int m = (l + r) >> 1 ;
    if(p<=m)    update(p, t, lson) ;
    else        update(p, t, rson) ;
    PushUp(rt) ;
}
int query(int L, int R, int l, int r, int rt){
    if(L<=l&&r<=R){
        return sum[rt] ;
    }
    int m = (l + r) >> 1 ;
    int ret = 0 ;
    if(L<=m)    ret = max(ret, query(L, R, lson)) ;
    if(R>m)     ret = max(ret, query(L, R, rson)) ;
    return ret ;
}
int main(){
    int n, m, i, j, a, b ;
    char c ;
    while(~scanf("%d%d", &n, &m)){
        build(1, n, 1) ;
        while(m--){
            c = getchar() ;
            scan_d(a) ;
            scan_d(b) ;
            if(c=='U')  update(a, b, 1, n, 1) ;
            else        printf("%d\n", query(a, b, 1, n, 1)) ;
        }
    }
    return 0 ;}