卢俊达

题目大意：

给定一个序列和两种操作：

Q操作，表示这是一条询问操作，询问区间[a,b]当中的元素的最大值是多少。

U操作，表示这是一条更新操作，要求把元素A的值更改为B。

思路：

线段树模板题。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define MAXSIZE 200000
int val[MAXSIZE+1];
struct node
{
	int max;
	int left;
	int right;
}tree[MAXSIZE*3];
int max(int x,int y)
{
	return x>y?x:y;
}
int create(int root,int left,int right)
//以root为根节点建树。 
{
	tree[root].left=left;
	tree[root].right=right;
	if(left==right)
		return tree[root].max=val[left];
	int a,b,middle=(left+right)/2;
	a=create(2*root,left,middle);
	b=create(2*root+1,middle+1,right);
	return tree[root].max=max(a,b);
}
int calculate(int root,int left,int right)
//以root为根节点的线段树中，求取区间[left,right]中的最大值。 
{
	if(tree[root].left>right||tree[root].right<left)
		return 0;
	if(left<=tree[root].left&&tree[root].right<=right)
		return tree[root].max;
	int a,b;
	a=calculate(2*root,left,right);
	b=calculate(2*root+1,left,right);
	return max(a,b);
}
int updata(int root,int pos,int val)
//以root为根节点的线段树中，将位置pos的元素更新为val。 
{
	if(pos<tree[root].left||tree[root].right<pos)
		return tree[root].max;
	if(tree[root].left==pos&&tree[root].right==pos)
		return tree[root].max=val;
	int a,b;
	a=updata(2*root,pos,val);
	b=updata(2*root+1,pos,val);
	return tree[root].max=max(a,b);
}
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&val[i]);
		create(1,1,n);
		for(int i=0;i<m;i++)
		{
			char op;
			int a,b;
			scanf("\n%c%d%d",&op,&a,&b);
			if(op=='Q')
				printf("%d\n",calculate(1,a,b));
			else
				updata(1,a,b);
		}
	}
}