HDU 1754 I Hate It
Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。在每个测试的第一行，有两个正整数 N 和 M ( 0
第二行包含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#include #include #include using namespace std; #define NUM 200000 int N, M; int S[4 * NUM], V[4 * NUM], R[4 * NUM], L[4* NUM]; void build(int n, int l, int r) { //建线段树 if (l == r) { R[n] = l; L[n] = l; S[n] = V[l - 1]; return ; } else { int temp = (l + r) / 2; R[2 * n + 1] = temp; R[2 * n + 2] = r; L[2 * n + 1] = l; L[2 * n + 2] = temp + 1; build(2 * n + 1, L[2 * n + 1] , R[2 * n + 1]); build(2 * n + 2, L[2 * n + 2], R[2 * n + 2]); S[n] = max(S[2 * n + 1], S[2 * n + 2]); } return ; } void modify(int n, int x, int v) { //将X改为V if (L[n] == x && R[n] == x) { S[n] = v; return; } int mid = (L[n] + R[n]) / 2; if (x <= mid) { modify(n * 2 + 1, x, v); } else { modify(n * 2 + 2, x, v); } S[n] = max(S[n * 2 + 1], S[n * 2 + 2]); } int cnt; int find(int n, int l, int r) { //查找区间l到r的最大值 if (l <= L[n] && r >= R[n]) { return S[n]; } int mid = (L[n] + R[n]) / 2; int min = -1; if (l <= mid) { min = max(min, find(n * 2 + 1, l, r)); } if (r > mid) { min = max(min, find(n * 2 + 2, l, r)); } return min; } int main() { while (scanf("%d %d\n", &N, & M) != EOF) { memset(S, 0, sizeof(S)); memset(V, 0, sizeof(V)); memset(R, 0, sizeof(R)); memset(L, 0, sizeof(L)); int cnt = 0; for (int i = 0; i < N; i++) { scanf("%d ", &V[cnt++]); } L[0] = 1; R[0] = cnt; build(0, L[0], R[0]); char ch; for (int i = 0; i < M; i++) { scanf("%c ", &ch); if (ch == 'Q') { int a, b; scanf("%d %d\n", &a, &b); printf("%d\n", find(0, a, b)); } else if (ch == 'U') { int a, b; scanf("%d %d\n", &a, &b); modify(0, a, b); } } } return 0; }