hdu1754 I Hate It(线段树单点更新，区间查询)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=200000+5;
 4 using namespace std;
 5 int a[maxn*4];
 6 const int INF=0x3f3f3f3f;
 7 void PushUp(int i)
 8 {
 9     a[i]=max(a[i*2],a[i*2+1]);
10 }
11 void build(int i,int l,int r)
12 {
13     if(l==r)
14     {
15         scanf("%d",&a[i]);
16         return;
17     }
18     int m=(l+r)/2;
19     build(i*2,l,m);
20     build(i*2+1,m+1,r);
21     PushUp(i);
22 }
23 int query(int ql,int qr,int i,int r)
24 {
25     if(ql<=l&&r<=qr)
26         return a[i];
27     int m=(l+r)/2;
28     int maxx=-INF;
29     if(ql<=m)
30         maxx=max(maxx,query(ql,qr,i*2,m));
31     if(qr>m)
32         maxx=max(maxx,i*2+1,r));
33     return maxx;
34 }
35 void update(int id,int val,int r)
36 {
37     if(l==r)
38     {
39         a[i]=val;
40         return;
41     }
42     int m=(l+r)/2;
43     if(id<=m)
44         update(id,val,m);
45     else
46         update(id,r);
47     PushUp(i);
48 }
49 int main()
50 {
51     int n,m;
52     while(~scanf("%d %d",&n,&m))
53     {
54         build(1,1,n);
55         while(m--)
56         {
57             char str[10];
58             int x,y;
59             scanf("%s%d%d",str,&x,&y);
60             if(str[0]==‘Q‘)
61                 printf("%dn",query(x,y,1,n));
62             else
63                 update(x,n);
64         }
65     }
66     return 0;
67 }