HDOJ 1754 I Hate It 线段树：单点轮换　成求段最值

HDOJ 1754 I Hate It 线段树：单点替换　成求段最值

//HDOJ 1754 I Hate It  线段树：单点替换　成求段最值
/*
题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1754

题目大意：有ｎ（0<ｎ<=200000）个学生，已知每个学生的初始成绩。
	有ｍ（0<ｍ<5000）次操作：	１、将ａ学生的成绩改为ｂ；
				２、查询区间[ａ,ｂ]中成绩最高的

思路：线段树叶子结点记录每个学生的成绩，父亲结点记录其两个子孩子中较高的成绩，这样根节点记录的就是所有成绩中最

高的。更新操作从根结点开始查找，一定在左孩子或右孩子其中一个，查询后替换，然后往上更新父结点。查询操作和敌兵布

阵一样，直至记录答案的时候不是累加结果，而是去更大的值，同样递归实现，时间复杂度Ｏ(logn);
*/

#include <stdio.h>
#define root 1
#define MAXN 600000

int n,m,x,y,a[MAXN];
int Max(int a,int b){
    return a>b?a:b;
}
struct node
{
    int left;
    int right;
    int max;
}t[MAXN];

int build(int p,int left,int right)
{
    t[p].left = left;
    t[p].right = right;
    if (left == right)
         return t[p].max = a[left];
    int m=(left+right)/2;
    return t[p].max = Max(build(p*2, left, m),build(p*2+1, m+1, right));
}

int query(int p, int left ,int right)
{    
    if (t[p].left==left && t[p].right==right)
        return t[p].max;
    int m=(t[p].left+t[p].right)/2;
    if (right<=m)
        return query(p*2,left,right);
    if (left>m)
        return query(p*2+1,left,right);
    return Max(query(p*2,left,m),query(p*2+1,m+1,right));
}

void update(int p,int x,int y)
{
    if (t[p].left == t[p].right)
        t[p].max=y;
    else
    {
        int m = (t[p].left+t[p].right) / 2;
        if(x<=m){
            update(p*2,x,y);
            t[p].max=Max(t[p].max,t[p*2].max);
        }
        else{
            update(p*2+1,x,y);
            t[p].max=Max(t[p].max,t[p*2+1].max);
        }
    }
}
int main()
{
    int i;
    char c;
    while(scanf("%d %d",&n,&m)==2)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        getchar();
        build(root,1,n);
        while(m--){    
            scanf("%c %d %d",&c,&x,&y);
            getchar();
            if(c=='Q')
                printf("%d\n",query(root,x,y));
            else
                update(root,x,y);    
        }
    }
    return 0;
}