HDU1754 I HATE IT【线段树】

题面：

Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0

大致思路：

依然是一个裸的线段树，点修改+区间询问，不过要求和上一题不一样。这个题求的是区间最大值。
把树中存的数改成区间最大值就OK了。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e5+10;
 4 int a[maxn],tree[maxn*4];
 5 void build(int l,int r,int k)
 6 {
 7     if(l>r)
 8         return ;
 9     if(l==r){
10         tree[k]=a[l];
11         return ;
12     }
13     int mid=(l+r)>>1;
14     build(l,mid,k*2);
15     build(mid+1,r,k*2+1);
16     tree[k]=max(tree[k*2],tree[k*2+1]);
17 }
18 void change(int pos,int x,int k,int l,int r)
19 {
20     if(l==r&&l==pos){
21         tree[k]=x;
22         return ;
23     }
24     int mid=(l+r)>>1;
25     if(pos<=mid)
26         change(pos,x,k*2,l,mid);
27     else
28         change(pos,x,k*2+1,mid+1,r);
29     tree[k]=max(tree[k*2],tree[k*2+1]);
30 }
31 int query(int l,int r,int ql,int qr,int k)
32 {
33     if(ql>r||qr<l)
34         return -1;
35     if(l>=ql&&r<=qr)
36         return tree[k];
37     int mid=(l+r)>>1;
38     int s1=query(l,mid,ql,qr,2*k);
39     int s2=query(mid+1,r,ql,qr,2*k+1);
40     return max(s1,s2);
41 }
42 int main()
43 {
44     //freopen("in.txt","r",stdin);
45     ios::sync_with_stdio(false);//不关闭同步有可能超时，也可以直接用scanf
46     int n,m,x,y;
47     char cmd;
48     while(cin>>n>>m)
49     {
50         for(int i=1;i<=n;++i)
51             cin>>a[i];
52         build(1,n,1);
53         while(m--)
54         {
55             cin>>cmd>>x>>y;
56             if(cmd=='Q')
57                 cout<<query(1,n,x,y,1)<<endl;
58             else
59                 change(x,y,1,1,n);
60         }
61     }
62     return 0;
63 }