题目描述
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。**
本题目包含多组测试
在每个测试的第一行，有两个正整数 N 和 M，分别代表学生的数目和操作的数目。学生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。 0~N~2e5，3~M~5e3。
对于每一次询问操作，在一行里面输出最高成绩。
【分析】：题目大意是给出n个数，有两种操作.
1：“U”，把某个元素修改为v；·2：“Q”， 计算max{Ai,Ai+1,…,Aj}.
最容易想到的算法是将成绩存到数组里，然后对于每一条查询，遍历数组的每一个元素。总时间复杂度是O(NM),实在是太大了。根据题目，我们可以用线段树来存储[x,y]区间中成绩的最大值，这样做的时间复杂度只有O（MlogN）。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000+10;
struct node//定义线段树
{
int s;//权值
int l,r;//左右子树权值
};
struct node tree[maxn*10];
int a[maxn];
int create_tree(int h,int x,int y)//建树(h为树编号)
{
tree[h].l=x;tree[h].r=y;//记录区间[l,r]
if(x==y)//叶子结点
{
tree[h].s=a[x];//记录权值
return tree[h].s;//返回权值
}
int mid=(x+y)/2;//取中点(int自动取整)
int x1=create_tree(h*2,x,mid);//左子树权值
int x2=create_tree(h*2+1,mid+1,y);//右子树权值
tree[h].s=max(x1,x2);//取更大值
return tree[h].s;//返回权值
}
int query(int h,int x,int y)//查询
{
if(y<tree[h].l||x>tree[h].r)//...x2---y2...l——r...x1---y1...
return 0;
if(x<=tree[h].l&&tree[h].r<=y)//达到范围...x---l——r---y...
return tree[h].s;//返回权值
int x1=query(2*h,x,y);//左子树
int x2=query(2*h+1,x,y);//右子树
return max(x1,x2);//返回权值
}
int update(int h,int x)//维护线段树
{
if(x<tree[h].l || x>tree[h].r)//超过范围...x1...l——r...x2...
return tree[h].s;//返回权值
if(tree[h].l==tree[h].r)//左右子树相同
{
tree[h].s=a[tree[h].l];//改权值
return tree[h].s;//返回权值
}
int x1=update(2*h,x);//左子树
int x2=update(2*h+1,x);//右子树
tree[h].s=max(x1,x2);//改权值
return tree[h].s;//返回权值
}
int main()
{
int i,j,k,m,n;int x,y;char c;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
create_tree(1,1,n);
for(i=1;i<=m;i++)
{
getchar();//过滤换行
scanf("%c%d%d",&c,&x,&y);//取得指令
if(c=='Q')
{printf("%d
",query(1,x,y));}
else
{a[x]=y;update(1,x);}
}
return 0;
}