B - I Hate It

多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.これは多くの学生に反感を抱かせた.あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の1行目には、2つの正の整数NとM(0学生ID番号はそれぞれ1からNに編成される.2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数はIDがiの学生の成績を表す.次はM行である.各行には1つの文字C(‘Q’または‘U’のみ)と2つの正の整数A,Bがある.Cが「Q」である場合、IDがAからB(A,Bを含む)までの学生の中で、成績が最も高いかを尋ねる質問操作であることを示す.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

 
 
この問題は線分の木のテンプレートの問題と言えるべきで、比較的に簡単で、線分の木を学んだばかりで、手を練習します

#include

using namespace std;

const int MAXN = 200000 + 10;
int  n , m;
int a[MAXN * 4];

void pushup(int x)
{
    a[x] = max (a[x << 1] , a[x << 1 | 1]);
}
void build(int left , int right ,int rt)
{
    if(left == right)
    {
        scanf("%d" , &a[rt]);
        return;
    }
    int mid = (left + right) >> 1;
    build(left , mid, rt << 1);
    build(mid + 1 , right , rt << 1 | 1);
    pushup(rt);
}

int que(int x , int y , int left , int right , int rt)
{
    if(left >= x && right <= y)
    {
        return a[rt];
    }
    int mid = (left + right) >> 1;
    int maxx = 0;
    if(mid >= x)
    {
        maxx = max(maxx , que(x , y , left , mid , rt << 1));
    }
    if(mid < y)
    {
        maxx = max (maxx , que(x , y , mid + 1 , right , rt << 1 | 1));
    }
    return maxx;

}

void data(int x , int k , int left , int right , int rt)
{
    if(left == right)
    {
        a[rt] = k;
        return;
    }
    int mid = (left + right) >> 1;
    if(mid < x)
        data(x , k , mid + 1, right , rt << 1 | 1);
    if(mid >= x)
        data(x , k , left , mid , rt << 1);
    pushup(rt);
}
int main()
{
    while(~scanf("%d %d" , &n , &m))
    {
        build(1, n , 1);
        char q;
        int  x , y ;
        while(m --)
        {
            cin >> q >> x >> y;
            if(q == 'Q')
            {
                printf("%d
" ,que(x , y , 1 , n , 1));
            }
            else
            {
                data(x , y , 1 , n , 1);
            }
        }
    }
}