HDu 1754 I Hate It(セグメントツリーポイントの更新と区間検索)

Problem Descriptionは多くの学校で比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.これは多くの学生に反感を抱かせた.
あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生は時々
ある同級生の成績を更新しなければならない.
Inputこの問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の第1行において、2つの正の整数NおよびMは、それぞれ学生の数および操作の数を表す.N<=20000,M<5000学生ID番号はそれぞれ1編からNまで.2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数はIDがiの学生の成績を表す.次はM行です.各行には、1文字C(Q’またはU’のみ)と、2つの正の整数A,Bがある.Cが‘Q’である場合、これはAからB(A,Bを含む)までのIDの学生の中で、成績が最も高いものはどれくらいかを尋ねる質問操作であることを示す.Cが‘U’である場合、IDがAの学生の成績をBに変更するように要求する更新操作であることを示す.
Outputは,問合せ操作ごとに1行に最高成績を出力する.
Sample Input 5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5
Sample Output 5 6 5 9
HintHuge input,the C function scanf() will work better than cin

#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int max(int a,int b)// 
{
    return a>b?a:b;
}
struct node
{
    int l,r;// [l,r]
    int w;// 
}t[800100];// 4 
int num[200010];
void build(int id,int l,int r)// id， [l,r] 
{
    t[id].l=l;
    t[id].r=r;
    if(l==r)
    {
        t[id].w=num[l];
        return ;
    }
    int mid=(l+r)/2;
    build(2*id,l,(l+r)/2);
    build(2*id+1,(l+r)/2+1,r);
    t[id].w=max(t[2*id].w,t[2*id+1].w);
}
int query(int id,int a,int b)// id [a,b] 
{
    if(t[id].l==a&&t[id].r==b)
        return t[id].w;
    int mid=(t[id].l+t[id].r)/2;
    if(b<=mid)
        return query(2*id,a,b);
    else if(a>=mid+1)
        return query(2*id+1,a,b);
    else
        return max(query(2*id,a,mid),query(2*id+1,mid+1,b));
}
void update(int id,int k,int nm)// id 
{
    if(t[id].l==k&&t[id].r==k)
    {
        t[id].w=nm;
        return ;
    }
    int mid=(t[id].l+t[id].r)/2;
    if(k<=mid)
        update(2*id,k,nm);
    else
        update(2*id+1,k,nm);
    t[id].w=max(t[2*id].w,t[2*id+1].w);
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);// scanf 
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            char ch;
            cin>>ch;
            int a,b;
            if(ch=='Q')
            {
                scanf("%d%d",&a,&b);
                cout<<query(1,a,b)<<endl;
            }
            else
            {
                cin>>a>>b;
                update(1,a,b);
            }
        }
    }
    return 0;
}