HDOJ 1754(セグメントツリー)

2749 ワード

タイトル:
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

   
   
   
   
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

解析:同1166,ノードが保持する値は区間最大値となる.
コード:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int MAX(int a, int b)
{
	return a > b ? a : b;
}
const int MAXN = 200001;
struct  
{
	int l, r, m;
}tree[MAXN*4];
int a[MAXN];
void creat(int root, int l, int r)
{
	tree[root].l = l;
	tree[root].r = r;
	if (l == r)
	{
		tree[root].m = a[l];
		return;
	}
	int m = (l + r) / 2;
	creat(root * 2, l, m);
	creat(root * 2 + 1, m + 1, r);
	tree[root].m = MAX(tree[root * 2].m, tree[root * 2 + 1].m);
}
void update(int root, int n, int v)
{
	if (tree[root].l == tree[root].r)
	{
		tree[root].m = v;
		return;
	}
	if (n <= tree[root * 2].r)
		update(root * 2, n, v);
	else
		update(root * 2 + 1, n, v);
	tree[root].m = MAX(tree[root * 2].m, tree[root * 2 + 1].m);
}
int query(int root, int l, int r)
{
	if (tree[root].l == l&&tree[root].r == r)
		return tree[root].m;
	int s;
	if (r <= tree[root * 2].r)
		s = query(root * 2, l, r);
	else if (l >= tree[root * 2 + 1].l)
		s = query(root * 2 + 1, l, r);
	else s = MAX(query(root * 2, l, tree[root * 2].r), query(root * 2 + 1, tree[root * 2 + 1].l, r));
	return s;
}
int main()
{
	int n, m,x1, x2;
	char s[2];
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		creat(1, 1, n);
		while (m--)
		{
			scanf("%s%d%d", s, &x1, &x2);
			if (s[0] == 'Q')
				printf("%d
", query(1, x1, x2)); else update(1, x1, x2); } } return 0; }