很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师的询问。当然,老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试,请处理到文件结束。
在每个测试的第一行,有两个正整数 N 和 M ( 0
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200020;
struct node {
int Max;
int l;
int r;
}tree[4*N];
int n, m ;
void build(int k,int ll,int rr){
tree[k].l=ll;
tree[k].r=rr;
if(tree[k].l==tree[k].r){
scanf("%d",&tree[k].Max);
return;
}
int m=(ll+rr)/2;
build(k*2,ll,m);
build(k*2+1,m+1,rr);
tree[k].Max=max(tree[k*2].Max,tree[k*2+1].Max);
}
inline int ask(int k,int a,int b){
if(tree[k].l>b|| tree[k].r<a){
return 0;
}
if(tree[k].l>=a && tree[k].r<=b){
return tree[k].Max;
}
int _a=ask(k*2, a,b);
int _b=ask(k*2+1,a,b);
return max(_a,_b);
}
inline int change_point(int k,int x,int y){
if(x<tree[k].l || x>tree[k].r){
return tree[k].Max;
}
if(tree[k].l==x && tree[k].r==x){
return tree[k].Max=y;
}
int _a=change_point(k*2,x,y);
int _b=change_point(k*2+1,x,y);
return tree[k].Max=max(_a,_b);
}
int main ()
{
char c ;
int i ;
int x, y ;
while (~scanf ("%d%d", &n, &m))
{
build (1, 1, n) ;
for (i = 1 ; i <= m ; ++i)
{
getchar () ;
scanf ("%c%d%d", &c, &x, &y) ;
if (c == 'Q')
{
printf ("%d\n", ask (1, x, y)) ;
}
else
{
change_point (1, x, y) ;
}
}
}
return 0 ;
}