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
Sample Output
解析:同1166,ノードが保持する値は区間最大値となる.
コード:
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
解析:同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;
}