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 ;
}