HDOJ 1754 线段树

I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 87335 Accepted Submission(s): 33441

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M ( 0

#include<bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1  
#define PI 3.1415926 
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const ll MAX = +;
int _max[MAX<<];
void PushUp(int rt){
    _max[rt]=max(_max[rt<<],_max[rt<<|]);
    return ;
}
void build(int l,int r,int rt){
    if(l == r){
        scanf("%d",&_max[rt]);
        return; 
    }
    int m = (l+r)>>;
    build(lson);
    build(rson); 
    PushUp(rt);
    return ;
}
void updata(int p,int np,int l,int r,int rt){
    if(l == r){
        _max[rt] = np;
        return ;
    }
    int m = (l+r)>>;
    if(p <= m) updata(p,np,lson);
    else updata(p,np,rson);
    PushUp(rt);
    return ;
}
int query(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R)
        return _max[rt];
    int ret = -;
    int m = (l+r)>>;
    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;
    while(~scanf("%d%d",&n,&m)){//
        build(,n,);
        char c[];
        int a,b; 
        while(m--){
            scanf("%s%d%d",c,&a,&b);
            if(c[] == 'Q') printf("%d\n",query(a,b,,n,));
            else updata(a,b,,n,);
        }   
    }
    return ;
}