HDu-1754-I Hate It(線分ツリー(単点更新))
1924 ワード
タイトル:
各試験の第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に変更する更新操作であることを示す.
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1754
——>>線分樹点修正、ラッキー、今回の再帰建樹はタイムアウトせず、437 MS過ぎ!
各試験の第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に変更する更新操作であることを示す.
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1754
——>>線分樹点修正、ラッキー、今回の再帰建樹はタイムアウトせず、437 MS過ぎ!
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 200000 + 10, INF = -214748364;
int a[maxn], maxv[4*maxn], A, B; //a ，maxv ，
void update(int o, int L, int R) // ， a[A] B
{
if(L == R) maxv[o] = B;
else
{
int M = L + (R - L) / 2;
if(A <= M) update(2*o, L, M);
else update(2*o+1, M+1, R);
maxv[o] = max(maxv[2*o], maxv[2*o+1]);
}
}
int query(int o, int L, int R) // [A, B]
{
if(A <= L && R <= B) return maxv[o];
int M = L + (R - L) / 2, ans = INF;
if(A <= M) ans = max(ans, query(2*o, L, M));
if(B > M) ans = max(ans, query(2*o+1, M+1, R));
return ans;
}
void build(int o, int L, int R) //
{
if(L == R)
{
maxv[o] = a[L];
return;
}
int M = L + (R - L) / 2;
if(L <= M) build(2*o, L, M);
if(R > M) build(2*o+1, M+1, R);
maxv[o] = max(maxv[2*o], maxv[2*o+1]);
}
int main()
{
int N, M;
char C;
while(~scanf("%d%d
", &N, &M))
{
for(int i = 1; i <= N; i++) scanf("%d", &a[i]);
build(1, 1, N);
while(M--)
{
scanf("
%c%d%d", &C, &A, &B);
if(C == 'U') update(1, 1, N);
else printf("%d
", query(1, 1, N));
}
}
return 0;
}