QUST日常訓練(1)点数修正
2807 ワード
タイトルの説明
多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を感じさせて、あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
入力
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の第1行において、2つの正の整数NおよびMは、それぞれ学生の数および操作の数を表す.学生ID番号はそれぞれ1編からNまでです.2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数aiはIDがiの学生の成績を表す.次はM行です.各行には1文字C('Q'または'U'のみ)と2つの正の整数A,Bがある.Cが「Q」である場合、IDがAからB(A,Bを含む)までの学生の中で、成績が最も高いかを尋ねる質問操作であることを示す.Cが「U」の場合、IDがAの学生の成績をBに変更する更新操作であることを示す.
しゅつりょく
対応する問い合わせを出力します.
サンプル入力
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
サンプル出力
5
6
5
9
ヒント
【データの説明】
30%のデータに対して、0
線分樹の単点更新と言えるでしょう、線分樹の中の水題
left,rightをbeginに変更し,endしてc++で空間を超えて実行する.の直しておけばよかったのに、憂鬱で、
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int segtree[800005];
void build(int left,int right,int node)
{
if(left == right)
{
scanf("%d",&segtree[node]); //
}
else
{
int m=(left+right)>>1;
build(left,m,node<<1);
build(m+1,right,node<<1|1); // |
segtree[node]=max(segtree[node<<1],segtree[node<<1|1]); //
}
}
void update(int p,int change,int left,int right,int node)
{
if(left==right)
{
segtree[node]=change;
}
else
{
int m=(left+right)>>1;
if(p<=m)update(p,change,left,m,node<<1);
else update(p,change,m+1,right,node<<1|1);
segtree[node]=max(segtree[node<<1],segtree[node<<1|1]); //
}
}
int query(int x,int y,int left,int right,int node)
{
if(x<=left && right<=y)
{
return segtree[node];
}
else
{
int sum=0,m=(left+right)>>1;
if(x<=m)sum=max(sum,query(x,y,left,m,node<<1));
if(y>m)sum=max(sum,query(x,y,m+1,right,node<<1|1));
return sum;
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(1,n,1);
while(m--)
{
char o[3];
int x,y;
scanf("%s%d%d",o,&x,&y);
if(o[0]=='U')
update(x,y,1,n,1);
else
printf("%d
",query(x,y,1,n,1));
}
}
return 0;
}