HDU 1754 i hate it
3708 ワード
I Hate It
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 20178 Accepted Submission(s): 8096
Problem Description
多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を抱かせた.
あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
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
Sample Output
セグメントツリー機能:update:単点置換query:区間最値
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 20178 Accepted Submission(s): 8096
Problem Description
多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を抱かせた.
あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各試験の第1行には、2つの正の整数NおよびM(0
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
Hint
Huge input,the C function scanf() will work better than cin
セグメントツリー機能:update:単点置換query:区間最値
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
#define lson l , m , rt<<1
#define rson m+1 , r , rt<<1|1
const int maxn = 222222;
int Max[maxn<<2];
int n,m;
void PushUP( int rt )
{
Max[rt] = max( Max[rt<<1] , Max[rt<<1|1] );
}
void build( int l , int r , int rt )
{
if( l == r )
{
scanf("%d",&Max[rt]);
return ;
}
int m = (l+r) >> 1;
build( lson );
build( rson );
PushUP( rt );
}
int query( int L , int R , int l , int r , int rt )
{
if( L <= l && r <= R )
{
return Max[rt];
}
int ret = 0;
int m = ( l+r ) >> 1;
if( L <= m )
ret = max(ret , query( L , R , lson ));
if( R > m )
ret = max(ret , query( L , R , rson ));
return ret;
}
void update( int p , int sc , int l , int r , int rt )
{
if( l == r )
{
Max[rt] = sc;
return ;
}
int m = ( l+r ) >> 1;
if( p > m )
update( p , sc , rson );
else
update( p , sc , lson );
PushUP( rt );
}
int main( )
{
while( scanf("%d%d",&n,&m) == 2 ){
build( 1 , n , 1 );
//for( int i=1 ; i<=n ; i++ )
// printf("%d
",Max[i]);
char op[5];
for( int i=0 ; i<m ; i++ ){
scanf("%s",op);
int a,b;
scanf("%d%d",&a,&b);
if( op[0] == 'Q' )
printf("%d
",query( a,b,1,n,1 ));
else if( op[0] == 'U' )
update( a,b,1,n,1 );
}
}
return 0;
}