题目链接： 

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

代码如下：

1 #include 
     
       2 #include  
      
        3 #include  
       
         4 #include  
        
          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     else33     {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\n", 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 }