题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754
题意：中文题诶～
思路：线段树单点替换&区间最大值查询模板
代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define lson l, mid, rt << 1 5 #define rson mid + 1, r, rt << 1 | 1 6 using namespace std; 7 8 const int MAXN = 2e5 + 10; 9 int Max[MAXN << 2];//Max[rt]存储rt对应区间的最大值 10 11 void push_up(int rt){//更新rt的值 12 Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]); 13 } 14 15 //建树 16 void build(int l, int r, int rt){//rt对应区间[l, r] 17 if(l == r){ 18 scanf("%d", &Max[rt]); 19 return; 20 } 21 int mid = (l + r) >> 1; 22 build(lson); 23 build(rson); 24 push_up(rt);//向上更新 25 } 26 27 //单点替换 28 void updata(int p, int sc, int l, int r, int rt){//将p点值替换成sc 29 if(l == r){//找到p点 30 Max[rt] = sc; 31 return; 32 } 33 int mid = (l + r) >> 1; 34 if(p <= mid) updata(p, sc, lson); 35 else updata(p, sc, rson); 36 push_up(rt);//向上更新节点 37 } 38 39 //求区间最值 40 int query(int L, int R, int l, int r, int rt){//查询[L, R]内最大值 41 if(L <= l && R >= r) return Max[rt];//当前区间[l, r]包含在[L, R]中 42 int cnt = 0; 43 int mid = (l + r) >> 1; 44 if(L <= mid) cnt = max(cnt, query(L, R, lson));//L在mid左边 45 if(R > mid) cnt = max(cnt, query(L, R, rson));//R在mid右边 46 return cnt; 47 } 48 49 int main(void){ 50 int n, m; 51 while(~scanf("%d%d", &n, &m)){ 52 // memset(Max, 0, sizeof(Max)); 53 build(1, n, 1); 54 char ch[2]; 55 int x, y; 56 while(m--){ 57 scanf("%s%d%d", ch, &x, &y); 58 if(ch[0] == 'U') updata(x, y, 1, n, 1); 59 else printf("%d ", query(x, y, 1, n, 1)); 60 } 61 } 62 return 0; 63 }