hdu 1754 I Hate It(线段树)

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

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 int tree[222222<<2];
 7 void push_up(int rt)
 8 {
 9     tree[rt]=max(tree[rt<<1],tree[rt<<1 | 1]);
10 }
11 void creat(int rt,int start,int end)
12 {
13     if(start==end)
14     {
15         scanf("%d",&tree[rt]);
16         return ;
17     }
18     else
19     {
20         //递归构造左右子树
21         creat(rt<<1,start,(start+end)>>1);
22         creat(rt<<1 | 1,((start+end)>>1)+1,end);
23         //回溯得到当前节点的信息
24         push_up(rt);
25     }
26 }
27 int recreach(int rt,int start,int end,int left,int right)
28 {
29     if(left>end||right<start)  //查询区间和要求区间没交集
30         return -1;
31     if(left<=start&&right>=end)
32         return tree[rt];
33     int mid=(start+end)>>1;
34     int ans=0;
35     if(left<=mid)
36         ans=max(ans,recreach(rt<<1,start,mid,left,right));
37     if(right>mid)
38         ans=max(ans,recreach(rt<<1 | 1,mid+1,end,left,right));
39     return ans;
40 }
41 void update(int rt,int start,int end,int a,int b)
42 {
43     if(start==end)
44     {
45         tree[rt]=b;
46         return ;
47     }
48     int mid=(start+end)>>1;
49     if(a<=mid)
50         update(rt<<1,start,mid,a,b);
51     else
52         update(rt<<1 | 1,mid+1,end,a,b);
53     push_up(rt);
54 }
55 int main()
56 {
57     int n,m;
58     char c[2];
59     int a,b;
60     while(~scanf("%d%d",&n,&m))
61     {
62         memset(tree,0,sizeof(tree));
63         creat(1,1,n);
64         while(m--)
65         {
66             scanf("%s%d%d",c,&a,&b);
67             if(c[0]=='Q')
68                 printf("%d
",recreach(1,1,n,a,b));
69             if(c[0]=='U')
70                 update(1,1,n,a,b);
71         }
72     }
73     return 0;
74 }

View Code