解题思路：求区间最大值，线段树模板题，不解释：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define inf 0x3f3f3f3f 6 #define lson l, m, rt << 1 7 #define rson m+1, r, rt << 1 | 1 8 const int maxn = 200005; 9 int A[maxn<<2], n, m, a, b; 10 char str[10]; 11 12 void Max(int rt) 13 { 14 A[rt] = max(A[rt<<1], A[rt<<1 | 1]); 15 } 16 17 void Build(int l, int r, int rt) 18 { 19 if(l == r) 20 { 21 scanf("%d", &A[rt]); 22 return ; 23 } 24 int m = (l + r) >> 1; 25 Build(lson); 26 Build(rson); 27 Max(rt); 28 } 29 30 void Update(int p, int score, int l, int r, int rt) 31 { 32 if(l == r) 33 { 34 A[rt] = score; 35 return ; 36 } 37 int m = (l + r) >> 1; 38 if(p <= m) Update(p, score, lson); 39 else Update(p, score, rson); 40 Max(rt); 41 } 42 43 int Query(int ll, int rr, int l, int r, int rt) 44 { 45 if(ll <= l && rr >= r) return A[rt]; 46 int m = (l + r) >> 1; 47 int max1 = -inf; 48 if(ll <= m) max1 = max(max1, Query(ll, rr, lson)); 49 if(rr > m) max1 = max(max1, Query(ll, rr, rson)); 50 return max1; 51 } 52 53 int main() 54 { 55 while(~scanf("%d %d", &n, &m)) 56 { 57 Build(1, n, 1); 58 while(m--) 59 { 60 scanf("%s%d%d", str, &a, &b); 61 if(str[0] == 'Q') 62 { 63 int ans = Query(a, b, 1, n, 1); 64 printf("%d ", ans); 65 } 66 else Update(a, b, 1, n, 1); 67 } 68 } 69 return 0; 70 }