hdu1754(线段树单点替换&区间最值模板)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754

题意：中文题诶～

思路：线段树单点替换&区间最大值查询模板

代码：

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 using namespace std;

 const int MAXN = 2e5 + ;

 int Max[MAXN << ];//Max[rt]存储rt对应区间的最大值

 void push_up(int rt){//更新rt的值

     Max[rt] = max(Max[rt << ], Max[rt <<  | ]);

 }

 //建树

 void build(int l, int r, int rt){//rt对应区间[l, r]

     if(l == r){

         scanf("%d", &Max[rt]);

         return;

     }

     int mid = (l + r) >> ;

     build(lson);

     build(rson);

     push_up(rt);//向上更新

 }

 //单点替换

 void updata(int p, int sc, int l, int r, int rt){//将p点值替换成sc

     if(l == r){//找到p点

         Max[rt] = sc;

         return;

     }

     int mid = (l + r) >> ;

     if(p <= mid) updata(p, sc, lson);

     else updata(p, sc, rson);

     push_up(rt);//向上更新节点

 }

 //求区间最值

 int query(int L, int R, int l, int r, int rt){//查询[L, R]内最大值

     if(L <= l && R >= r) return Max[rt];//当前区间[l, r]包含在[L, R]中

     int cnt = ;

     int mid = (l + r) >> ;

     if(L <= mid) cnt = max(cnt, query(L, R, lson));//L在mid左边

     if(R > mid) cnt = max(cnt, query(L, R, rson));//R在mid右边

     return cnt;

 }

 int main(void){

     int n, m;

     while(~scanf("%d%d", &n, &m)){

         // memset(Max, 0, sizeof(Max));

         build(, n, );

         char ch[];

         int x, y;

         while(m--){

             scanf("%s%d%d", ch, &x, &y);

             if(ch[] == 'U') updata(x, y, , n, );

             else printf("%d\n", query(x, y, , n, ));

         }

     }

     return ;

 }