很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0 < N <= 200000,0 < M < 5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。
当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作，在一行里面输出最高成绩。
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
单点更新，区间求最值，标准的线段树模板题。
直接打上模板按要求做更新和查询的操作即可
#include<stdio.h>///取最大值
#include<string.h>
#include<algorithm>
#define N 200000
using namespace std;
struct tree
{
int l,r,maxx;
} a[N*4];///四倍的原题最大值
int b[200003];///存储每人成绩的数组
void build(int l,int r,int root)///建树
{
a[root].l=l;///左右范围赋值
a[root].r=r;
a[root].maxx=-1;///最大值初始化
if(l==r)///叶子节点被赋予数组成绩
{
a[root].maxx=b[l];
}
else///不是叶子节点继续二分
{
int mid=(l+r)/2;///中点
build(l,mid,root*2);///左儿子
build(mid+1,r,root*2+1);///右儿子 递归建树
a[root].maxx=max(a[root*2].maxx,a[root*2+1].maxx);///递归完成后取建好的数中的底层一步步向上传递取最值
}
}
void upda(int where , int value , int root)///单点更新
{
if(a[root].l == a[root].r)///需要更新的叶子节点
{
a[root].maxx = value ;
return ;///递归终点
}
int mid = (a[root].l+a[root].r)/2 ;///这里又是递归更新了，换句话说，尼玛建树更新和查找其实都有这个步骤
if(where<=mid) upda(where,value,root*2);///当目的区间小于中点，向左儿子搜索
else upda(where,value,root*2+1);///否则向右儿子搜索
a[root].maxx = max(a[root*2].maxx , a[root*2+1].maxx);///已经有了向上传递的操作
}///由下至上递归返回更新
//void pushup(int root)///向上传递
//{
// if(a[root].l==a[root].r)return;
// a[root].maxx=max(a[root*2].maxx,a[root*2+1].maxx);
//}
int query(int l,int r,int root)///区间查询
{
if(l<=a[root].l&&a[root].r<=r)///在包含区间内查询到目的区间
{
return a[root].maxx;
}
else
{
int mid = (a[root].l+a[root].r)/2;
int res=-1;///初始化最值记录
if(l<=mid)
{
res = max(query(l,r,root*2),res);///查询时注意目标区间不要改变，课件中mid+1与mid是改变了的，会WA
}
if(r>=mid+1)
{
res = max(query(l,r,root*2+1),res);
}
return res;///返回最大值
}
}
int main()
{
int n,i,j,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1; i<=n; i++)///输入每人成绩
{
scanf("%d",&b[i]);
}
build(1,n,1);///建树
// for(i=1; i<=n; i++)
// {
// printf("=====
");
// printf("%d
",a[i].maxx);
// }
char commed[2];///指令，为防止getchar情况而设成数组
while(m--)
{
scanf("%s",commed);
if(commed[0]=='U')///更新指令
{
scanf("%d%d",&i,&j);
upda(i,j,1);
// pushup(1);
// for(i=1; i<=n; i++)
// {
// printf("=====
");
// printf("%d
",a[i].maxx);
// }
}
else if(commed[0]=='Q')///查询指令
{
scanf("%d%d",&i,&j);
int maxy=query(i,j,1);
printf("%d
",maxy);
}
}
}
return 0;
}