I Hate It（HDOJ 1754）
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
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 Hint Huge input,the C function scanf() will work better than cin
My Code
线段树的另一种常见运用，求最大值，很多对连续区间的修改和询问都可以用线段树来优化。
#include
#include
#include
#define maxn 200005
using namespace std;
struct node
{
int v;
int l;
int r;
} tree[maxn << 2];
int a[maxn];
int n, m;
void build_tree(int l, int r, int id)
{
tree[id].l = l;
tree[id].r = r;
if (l == r)
{
tree[id].v = a[l];
return;
}
int m = (l + r) >> 1;
build_tree(l, m, id << 1);
build_tree(m + 1, r, id << 1 | 1);
tree[id].v = max(tree[id << 1].v, tree[id << 1 | 1].v);
}
int query(int l, int r, int id)
{
if (tree[id].l > r || tree[id].r < l)
return 0;
if (l <= tree[id].l && tree[id].r <= r)
return tree[id].v;
int m = (tree[id].l + tree[id].r) >> 1;
return max(query(l, r, id << 1), query(l, r, id << 1 | 1));
}
void update(int i, int v, int id)
{
if (tree[id].l == tree[id].r)
{
tree[id].v = v; //因为是修改所以直接赋值
return;
}
int m = (tree[id].l + tree[id].r) >> 1;
if (i <= m)
update(i, v, id << 1);
else
update(i, v, id << 1 | 1);
tree[id].v = max(tree[id << 1].v, tree[id << 1 | 1].v);
}
int main()
{
while (~scanf("%d%d", &n, &m)) //多组数据
{
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]); //数据较大用scanf
getchar(); //两个getchar()把回车吃了
build_tree(1, n, 1);
for (int i = 0; i < m; i++)
{
char c;
int b, d;
scanf("%c%d%d", &c, &b, &d);
getchar();
if (c == 'Q')
printf("%d
", query(b, d, 1));
else if (c == 'U')
update(b, d, 1);
}
}
return 0;
} 
OωO
