HDu 1754 I Hate It(線分木単点修正、区間最値)

5857 ワード

セグメントツリー&ツリー配列&議長ツリー

Problem Descriptionは多くの学校で比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.これは多くの学生に反感を抱かせた.
あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
Inputこの問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の第1行には、2つの正の整数NおよびM(0Outputは,問合せ操作ごとに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
Hint Huge input,the C function scanf() will work better than cin
考え方:単純な線分ツリーテンプレート
コードは次のとおりです.

#include 
#include 
#include   
#include   
#include
#define M 200005  
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  
using namespace std;

int Max[M<<2];  
int A[M];  
inline void PushPlus(int rt)  
{   
    Max[rt] = max(Max[rt<<1],Max[rt<<1|1]); 
}  

void Build(int l, int r, int rt)  //  
{  
    if(l == r)  
    {    
        Max[rt]=A[l];
        return ;  
    }  
    int m = ( l + r )>>1;  

    Build(lson);  
    Build(rson);  
    PushPlus(rt);  
}  

void Updata(int p, int change, int l, int r, int rt)// ,p change 
{  

    if( l == r )  
    {   
        Max[rt]=change;
        return ;  
    }  
    int m = ( l + r ) >> 1;  
    if(p <= m)  
        Updata(p, change, lson);  
    else  
        Updata(p, change, rson);  

    PushPlus(rt);  
}  

int Query(int L,int R,int l,int r,int rt)  
{  
    if( L <= l && r <= R )  
    {  
        return Max[rt];  
    }  
    int m = ( l + r ) >> 1;  
    int ans=0;  
    if(L<=m )  
        ans=max(ans,Query(L,R,lson));  
    if(R>m)  
        ans=max(ans,Query(L,R,rson));  

    return ans;  
}  
int main()  
{     
    int n,m; 
    while(scanf("%d%d",&n,&m)!=EOF)
    {

        for(int i=1;i<=n;i++)
            scanf("%d",&A[i]); 
        Build(1,n,1);  
        while(m--)  
        {  
            int a,b;
            char op[2];
            scanf("%s%d %d",op,&a,&b);  
            if(op[0]=='Q')  
                printf("%d
",Query(a,b,1,n,1));  
            else 
                Updata(a,b,1,n,1);  
        }  
    }
    return 0;  
}

Lenovo ThinkServer RS 260サーバー静音ノイズ低減改造及びCentOSコピー機テスト

wordpress、帝国cmsサイト構成https(SSL)バックグラウンドにログインできません