QUST日常訓練(1)点数修正

2807 ワード

タイトルの説明


多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を感じさせて、あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.

入力


この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の第1行において、2つの正の整数NおよびMは、それぞれ学生の数および操作の数を表す.学生ID番号はそれぞれ1編からNまでです.2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数aiはIDがiの学生の成績を表す.次はM行です.各行には1文字C('Q'または'U'のみ)と2つの正の整数A,Bがある.Cが「Q」である場合、IDがAからB(A,Bを含む)までの学生の中で、成績が最も高いかを尋ねる質問操作であることを示す.Cが「U」の場合、IDがAの学生の成績をBに変更する更新操作であることを示す.

しゅつりょく


対応する問い合わせを出力します.

サンプル入力


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

サンプル出力


5
6
5
9

ヒント


【データの説明】
 
30%のデータに対して、060%のデータに対して、0100%のデータに対して、0分析:線分樹問題(最初の線分樹...各種バグが頻出...涙が走る...無言)
線分樹の単点更新と言えるでしょう、線分樹の中の水題
left,rightをbeginに変更し,endしてc++で空間を超えて実行する.の直しておけばよかったのに、憂鬱で、
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;


int segtree[800005];
void build(int left,int right,int node)
{
    if(left == right)
    {
        scanf("%d",&segtree[node]);  // 
    }
    else
    {
        int m=(left+right)>>1;
        build(left,m,node<<1);
        build(m+1,right,node<<1|1);  // |  
        segtree[node]=max(segtree[node<<1],segtree[node<<1|1]); // 
    }
}

void update(int p,int change,int left,int right,int node)
{
    if(left==right)
    {
        segtree[node]=change;
    }
    else
    {
        int m=(left+right)>>1;
        if(p<=m)update(p,change,left,m,node<<1);
        else update(p,change,m+1,right,node<<1|1);
        segtree[node]=max(segtree[node<<1],segtree[node<<1|1]);   // 
    }
}

int query(int x,int y,int left,int right,int node)
{
    if(x<=left && right<=y)
    {
        return segtree[node];
    }
    else
    {
        int sum=0,m=(left+right)>>1;
        if(x<=m)sum=max(sum,query(x,y,left,m,node<<1));
        if(y>m)sum=max(sum,query(x,y,m+1,right,node<<1|1));
        return sum;
    }
}

int main()
{

    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,n,1);
        while(m--)
        {
            char o[3];
            int x,y;
            scanf("%s%d%d",o,&x,&y);
            if(o[0]=='U')
                update(x,y,1,n,1);
            else
                printf("%d
",query(x,y,1,n,1)); } } return 0; }