hdu 1754 I Hate It

线段树模板题。该题是对点进行更新，对区间进行查询，在初始化时为了方便把n扩充为了2的整数次幂。并且注意线段树应该开辟4倍于n的数组来存储。注意对于输入字符'Q','U'，一定不能用char c;scanf("%c",&c);来接收，这样会接收到上次输入的回车。正确的方法是使用char s[3];scanf("%s",s);，这个bug我找了好久才发现。

代码如下：

 1 #include <cstdlib>
 2 #include  <cstdio>
 3 #include  <iostream>
 4 #include  <cstring>
 5 using namespace std;
 6 const int MAX_N = 1 << 20 ;
 7 int n, dat[MAX_N * 2 -1];
 8 const int MIN = -1;
 9 void init(int n_)
10 {
11     n = 1;
12     while(n < n_) n*=2;
13     for( int i = 0 ; i < 2 * n -1 ; i++ )
14     {
15         dat[i] = MIN;
16     }
17 }
18 void update(int k, int a)
19 {
20     k += n - 1;
21     dat[k] = a;
22     while( k > 0 )
23     {
24         k = (k-1)/2;
25         dat[k] = max(dat[k*2+1], dat[k*2+2]);
26     }
27 }
28 int query(int a, int b, int k, int l, int r)
29 {
30     if( r <= a || b <= l ) return MIN;
31     if( a <= l && r <= b ) return dat[k];
32     else
33     {
34         int vl = query(a, b, k * 2 + 1, l, (l+r)/2);
35         int vr = query(a, b, k * 2 + 2, (l+r)/2, r);
36         return max(vl, vr);
37     }
38 }
39 int main(int argc, char *argv[])
40 {
41     int N, M;
42     while(scanf("%d%d", &N,&M ) != EOF)
43     {
44         int tmp;
45         init(N);
46         for( int i = 0 ; i < N ; i++ )
47         {
48             scanf ( "%d", &tmp );
49             update(i,tmp); 
50         }
51         char c[5];
52         for( int i = 0 ; i < M ; i++ )
53         {
54             scanf ( "%s", c );
55             if(!strcmp(c ,"Q"))
56             {
57                 int l, r;
58                 scanf ( "%d%d", &l, &r);
59                 printf("%d
", query(l-1, r, 0, 0, n));
60             }
61             else if( !strcmp(c , "U" ))
62             {
63                 int a, b;
64                 scanf ( "%d%d", &a, &b );
65                 update(a-1, b);
66             }
67         }
68     }
69 }