hdu 1754 I Hate It (线段树求区间最值)

HDU1754 I Hate It

Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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 

入门级的线段树求区间最值，注释都在代码中了....

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <climits>
 8 #include <queue>
 9 
10 using namespace std;
11 
12 const int MAX = 200005;
13 struct nodes
14 {
15     int left,right,large;
16 }tree[MAX*20];
17 
18 int n,m,num[MAX];
19 
20 int build(int root,int left,int right)//构建线段树
21 {
22     int mid;
23     tree[root].left = left;
24     tree[root].right = right;//当前区间
25     if(left == right)
26         return tree[root].large = num[left];//递归到最底层，把初始值赋值给当前节点
27 
28     mid = (left+right)/2;//划分成左右两个区间
29     int a,b;
30     a = build(2*root,left,mid);//划分区间，左节点继续往下递归
31     b = build(2*root+1,mid+1,right);//右节点向下递归
32 
33     return tree[root].large = max(a,b);//返回当前区间最大值，并给当前节点赋值
34 }
35 
36 int find(int root ,int left,int right)//查找区间最值
37 {
38 
39     if(tree[root].left > right || tree[root].right < left)//所查区间不在范围内，返回0
40         return 0;
41     if(left <= tree[root].left && right >= tree[root].right)//刚好查到当前区间，返回区间最大值
42         return tree[root].large;
43     int a,b;
44     a = find(2*root,left,right);//如果所查区间分布在划分区间的两边，则分开查找最大值
45     b = find(2*root+1,left,right);
46     return max(a,b);//比较返回最大值
47 }
48 
49 int update(int root,int pos,int val)//更新区间最值
50 {
51     if(pos <tree[root].left || pos > tree[root].right)
52         return tree[root].large;
53     if(pos == tree[root].left && pos == tree[root].right)//递归到需要修改的位置，修改节点值并返回
54         return tree[root].large = val;
55 
56     int a,b;
57     a = update(2*root,pos,val); //递归向下修改左节点值，并返回修改后的区间最值
58     b = update(2*root+1,pos,val);//递归向下修改右节点值，并返回修改后的区间最值
59     tree[root].large = max(a,b); //更新节点最大值
60     return tree[root].large;//返回当前节点最大值
61 }
62 
63 
64 int main(void)
65 {
66     int m,n,i,x,y;
67     char ch;
68     while(scanf("%d %d",&n,&m) != -1)
69     {
70         for(i = 1; i <= n; i++)
71             scanf("%d",&num[i]);
72         build(1,1,n);
73         for(i = 0; i < m; i++)
74         {
75             getchar();
76             scanf("%c",&ch);
77             scanf("%d %d",&x,&y);
78             if(ch == 'Q')
79                 printf("%d
",find(1,x,y));
80             else
81             {
82                 num[x] = y;
83                 update(1,x,y);
84             }
85         }
86     }
87     return 0;
88 }