Problem 1689スコア修正
5135 ワード
質問B:スコア修正
時間制限:1 Sec
メモリ制限:128 MB
タイトルの説明
多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を感じさせて、あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
入力
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の第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 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
サンプル出力
5659
ヒント
【データの説明】
30%のデータに対して、0
そしてサンプルを过ぎてTLEはこれでとてもつらいです><....
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int data[200001];
struct node
{
int start,end;
int max;
int left,right;
};
node tree[400002];
int cnt=0;
int fillnode(int leftbound,int rightbound)
{
//if(leftbound>rightbound) throw "d";
tree[cnt].start=leftbound;
tree[cnt].end=rightbound;
tree[cnt].max=-1;
if(leftbound==rightbound)
{
tree[cnt].left=-1;
tree[cnt].right=-1;
cnt++;
return cnt-1;
}
cnt++;
int cur=cnt-1;
tree[cur].left=fillnode(leftbound,(leftbound+rightbound)/2);
tree[cur].right=fillnode((leftbound+rightbound)/2+1,rightbound);
return cur;
}
void change(int targetpos,int value,int nodepos)
{
#if 0
printf("%d %d %d
",targetpos,value,nodepos);
#endif //
if(value>tree[nodepos].max)
{
tree[nodepos].max=value;
}
if(tree[nodepos].left==-1)
{
/// reach this point
tree[nodepos].max=value;
return;
}
if(targetpos<=tree[tree[nodepos].left].end)
{
change(targetpos,value,tree[nodepos].left);
}
else
{
change(targetpos,value,tree[nodepos].right);
}
}
int findmax(int leftbound,int rightbound,int nodepos)
{
if(tree[nodepos].left==-1)
{
return tree[nodepos].max;
}
if(rightbound<=tree[tree[nodepos].left].end)
{
/// Full left
return findmax(leftbound,rightbound,tree[nodepos].left);
}
if(leftbound>=tree[tree[nodepos].right].start)
{
/// Full right
return findmax(leftbound,rightbound,tree[nodepos].right);
}
/// Half left and half right
int leftmax=findmax(leftbound,tree[tree[nodepos].left].end,tree[nodepos].left);
int rightmax=findmax(tree[tree[nodepos].right].start,rightbound,tree[nodepos].right);
return leftmax>rightmax?leftmax:rightmax;
}
char buff[8];
int eax,ebx;
int main()
{
fillnode(1,200000);
int n,m;
while(scanf("%d %d",&n,&m)==2)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&data[i]);
change(i,data[i],0);
}
for(int i=0;i<m;i++)
{
scanf("%s %d %d",buff,&eax,&ebx);
switch(buff[0])
{
case 'U':
change(eax,ebx,0);
break;
case 'Q':
/// Find Max from [eax,ebx]
int ans=findmax(eax,ebx,0);
printf("%d
",ans);
break;
}
}
for(int i=0;i<200001;i++)
{
/// Reset the tree.
tree[i].max=-1;
}
}
return 0;
}
皮肉なことに...一番簡単なものは...ACだ...
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
long score[200001];
char ppp[4];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)==2)
{
for(int i=1; i<=n; i++)
{
scanf("%ld",&score[i]);
}
long eax,ebx;
for(int q=0; q<m; q++)
{
scanf("%s %ld %ld",ppp,&eax,&ebx);
switch(ppp[0])
{
case 'U':
score[eax]=ebx;
break;
case 'Q':
long max=-1;
for(int i=eax; i<=ebx; i++)
{
if(max<score[i])
{
max=score[i];
}
}
printf("%ld
",max);
break;
}
}
}
return 0;
}