hdu 1754(单点更新)

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define MAXN 200010
#define Lson(x) (x<<1)
#define Rson(x) (Lson(x)|1)
#define Mid(x,y) ((x+y)>>1)


int num[MAXN], n, m;

struct Node{
    int left;
    int right;
    int maxs;
}node[4 * MAXN];

void (int pos)
{
    node[pos].maxs = max(node[Lson(pos)].maxs, node[Rson(pos)].maxs);
}

void build_tree(int left, int right, int pos)
{
    node[pos].left = left;
    node[pos].right = right;
    if(left == right){
        node[pos].maxs = num[left];
        return ;
    }
    int x = Mid(left, right);
    build_tree(left, x, Lson(pos));
    build_tree(x + 1, right, Rson(pos));
    push_up(pos);
}

void update(int index, int val, int pos)
{
    if(node[pos].left ==  node[pos].right){
        node[pos].maxs = val;
        //printf("haha : %dn", node[pos].maxs);
        return ;
    }
    int mid = Mid(node[pos].left, node[pos].right);
    if(index <= mid)
        update(index, val, Lson(pos));
    else
        update(index, val, Rson(pos));
    push_up(pos);
}

int query(int left, int right, int pos)
{
    if(node[pos].left == left && node[pos].right == right)
        return node[pos].maxs;
    int mid = Mid(node[pos].left, node[pos].right);
    if(right <= mid)
        return query(left, right, Lson(pos));
    else if(mid < left)
        return query(left, right, Rson(pos));
    else
        return max(query(left, mid, Lson(pos)), query(mid + 1, right, Rson(pos)));

}

void input()
{
    char ch;
    int x, y;
    for(int i = 1 ; i <= n ; i++)
        scanf("%d" , &num[i]);
    getchar();
    build_tree(1 , n , 1);
    while(m--){
        scanf("%c%d%d" , &ch , &x , &y);
        getchar();
        if(ch == 'Q'){
            printf("%dn" , query(x , y , 1));
        }
        else
            update(x , y , 1);
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &n, &m) != EOF){
        input();
    }
    return 0;
}