hdu 1754 I Hate It【线段树】

维护一个最大值
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 #define lp (p << 1)
 8 #define rp (p << 1 | 1)
 9 #define getmid(l,r)  l+(r-l)/2
10 
11 const int maxn = 200005;
12 const int INF = 1000000000;
13 struct node{
14     int l,r,maxx;
15 }t[4*maxn];
16 
17 int n,m,nmax;
18 int a[maxn];
19 
20 void Push_up(int p){
21     t[p].maxx = max(t[lp].maxx,t[rp].maxx);
22 }
23 
24 void Build_tree(int p,int l,int r){
25     t[p].l = l;
26     t[p].r = r;
27     if(l == r){
28         t[p].maxx = a[l];
29         return;
30     }
31     int mid = getmid(l,r);
32     Build_tree(lp,l,mid);
33     Build_tree(rp,mid+1,r);
34     Push_up(p);
35 }
36 
37 void Update(int p,int s,int w){
38     if(t[p].l == t[p].r){
39         t[p].maxx = w;
40         return;
41     }
42     int mid = getmid(t[p].l,t[p].r);
43     if(s <= mid) Update(lp,s,w);
44     else Update(rp,s,w);
45     Push_up(p);
46 }
47 
48 void Query(int p,int l,int r){
49     if(t[p].maxx <= nmax) return;
50     if(t[p].l == l && t[p].r == r ){
51         nmax = max(t[p].maxx,nmax);
52         return;
53     }
54     int mid = getmid(t[p].l,t[p].r);
55     if(r <= mid) Query(lp,l,r);
56     else if(l > mid) Query(rp,l,r);
57     else{
58         Query(lp,l,mid);
59         Query(rp,mid+1,r);
60     }
61 }
62 
63 int main(){
64     while(scanf("%d %d",&n,&m) != EOF){
65         for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
66         Build_tree(1,1,n);
67     
68         char ch;
69         int x,y;
70         while(m--){
71             cin>>ch>>x>>y;
72             if(ch == 'Q') {
73                 nmax = -INF;
74                 Query(1,x,y);
75                 printf("%d
",nmax);
76             }
77             else Update(1,x,y);
78         }
79     }
80     return 0;
81 }
View Code
加油～～坚持每天三颗树～
gooooo-----