HDU-1754 I Hate It ( 线段树 )

 1 #include<iostream>
 2 using namespace std;
 3 
 4 const int MAX = 200005;
 5 class Node{
 6 public:
 7     int l,r,v;
 8 }node[MAX * 3];
 9 int num[MAX];
10 
11 int max( int a,int b ){
12     return a > b ? a : b;
13 }
14 
15 void Creat( int i, int z, int y ){
16     node[i].l = z;
17     node[i].r = y;
18     
19     if( z == y ){
20         node[i].v = num[z];
21         return;
22     }
23 
24     int mid = ( z + y ) >> 1;
25     Creat( i << 1, z, mid );
26     Creat( ( i << 1 ) + 1, mid + 1, y );
27     node[i].v = max( node[i << 1].v, node[( i << 1 ) + 1].v );
28 }
29 
30 void Insert( int i, int x, int n ){
31     if( node[i].l == node[i].r ){
32         node[i].v = n;
33         return;
34     }
35 
36     int mid = ( node[i].l + node[i].r ) >> 1;
37     if( x <= mid ) Insert( i << 1, x, n );
38     else Insert( ( i << 1 ) + 1, x, n );
39 
40     node[i].v = max( node[i << 1].v, node[( i << 1 ) + 1].v );
41 }
42 
43 int Ask( int i, int z, int y ){
44     if( node[i].l == z && node[i].r == y )
45         return node[i].v;
46 
47     int mid = ( node[i].l + node[i].r ) >> 1;
48 
49     if( y <= mid )
50         return Ask( i << 1, z, y );
51     else if( z > mid )
52         return Ask( ( i << 1 ) + 1, z, y );
53     else 
54         return max( Ask( i << 1, z, mid ), Ask( ( i << 1 ) + 1, mid + 1, y ) );
55 }
56 
57 int main(){
58     ios::sync_with_stdio( false );
59     
60     int N, M;
61     while( cin >> N >> M ){
62         
63         for( int i = 1; i <= N; i++ )
64             cin >> num[i];
65         Creat( 1, 1, N );
66 
67         char k;
68         int a, b;
69 
70         for( int i = 1; i <= M; i++ ){
71             cin >> k >> a >> b;
72 
73             if( k == ‘Q‘ ) cout << Ask( 1, a, b) << endl;
74             else Insert( 1, a, b );
75         }
76     }
77     return 0;
78 }