I Hate It(ワンポイント更新)


テーマリンク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’である場合、これは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
#include
using namespace std;
const int N = 200005;
char c;
int n,m,p,q,a[N],mx[N << 2];
void build(int k,int l,int r){
	if(l == r){
		mx[k] = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(k * 2,l,mid);
	build(k * 2 + 1,mid + 1,r);
	mx[k] = max(mx[k * 2],mx[k * 2 + 1]);
	return;
}
int query(int k,int l,int r,int L,int R){
	if(l > R || r < L){
		return 0;
	}
	if(L <= l && R >= r){
		return mx[k];
	}
	int mid = l + r >> 1;
	return max(query(k * 2,l,mid,L,R),query(k * 2 + 1,mid + 1,r,L,R));
}
void update(int k,int l,int r,int L,int R){
	if(l == r){
		mx[k] = R;
		return;
	}
	int mid = l + r >> 1;
	if(mid >= L){
		update(k * 2,l,mid,L,R);
	}
	else{
		update(k * 2 + 1,mid + 1,r,L,R);
	}
	mx[k] = max(mx[k * 2],mx[k * 2 + 1]);
	return;
}
int main(){
	ios :: sync_with_stdio(false);
	cin.tie(0);
	while(cin >> n >> m){// 
		for(int i = 1;i <= n;i++){
			cin >> a[i];
		}
		build(1,1,n);
		for(int i = 0;i < m;i++){
			cin >> c >> p >> q;
			if(c == 'Q'){
				cout << query(1,1,n,p,q) << endl;
			}
			else{
				update(1,1,n,p,q);
			}
		}
	}		
	return 0;
}