又是一个线段树的应用，不过跟上一题（D-排兵布阵）不同的是，这次是求某段区间上的最值，而不是某段区间和。当然，数据更新是必须的。D题注释已经很详细了，所以这题注释少点。
大致题意：给你N个已经排好的学生成绩，然后有M条指令，输出对应指令的结果。指令有两种：
1.Q i j：询问i到j的最值
2.U i j：把学生编号为i的成绩改为j
输入输出格式：
Sample Input
5 6 //第一行两个整数N,M，表示N个学生和M条指令( 0<N<=200000,0<M<5000 )
1 2 3 4 5 //第二行是N个学生的成绩（对应学生编号）
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> int max(int a,int b)//首先定义一个取最大值的函数
{
return a>b?a:b;
} struct tree
{
int l,r,s;
}; char s[];
int m,n,x,y;
tree t[];//一般存节点的数组是叶子节点的三倍就够了 void Init(int l,int r,int k)//构造线段树
{
t[k].l=l;
t[k].r=r;
if(l==r)//叶子节点
{
int x;
scanf("%d",&x);
t[k].s=x;//输入该叶子节点（学生）的分数
return ;
}
int mid=(l+r)/;
Init(l,mid,k*);//构造左子树
Init(mid+,r,k*+);//构造右子树
t[k].s=max(t[k*].s,t[k*+].s);//更新父节点数据（取最大值）
} void updata(int c,int x,int k)//数据的更新操作
{
if(t[k].l==t[k].r&&t[k].l==c)
{
t[k].s=x;
return ;
}
if(c<t[k].l||c>t[k].r)
return ;
updata(c,x,k*);
updata(c,x,k*+);
t[k].s=max(t[k*].s,t[k*+].s);
} int query(int l,int r,int k)//数据查询 注意范围落在哪个区间就行了
{
if(t[k].l==l&&t[k].r==r)
return t[k].s;
int mid=(t[k].l+t[k].r)/;
if(r<=mid)
return query(l,r,k*);
else if(l>=mid+)
return query(l,r,k*+);
else
return max(query(l,mid,k*),query(mid+,r,k*+));
} int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
Init(,n,);
while(m--)
{
scanf("%s %d %d",&s,&x,&y);
if(s[]=='U')
updata(x,y,);
else
printf("%d\n",query(x,y,));
}
}
return ;
}