I Hate It HDU - 1754

这题涉及单点更新，相对来说比较容易把

/*If I get TLE , it is good.If I get AC,it's NICE !*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
const int MAXN=1e6+100;
struct t
{
    int l,r,v;
} sgetree[800000+5];
int a[300000+5];
int index,grade;
int l,r;
int ans=0;
using namespace std;

//询问主要是把一个区间拆成几个区间去找，然后找到每个子区间的ans，找最大的
void query(int l,int r,int root)
{
    if(sgetree[root].l==l && sgetree[root].r==r)
    {
        ans=max(ans,sgetree[root].v);
        return ;
    }
    int mid=(sgetree[root].l+sgetree[root].r)/2;
    if(r<=mid) query(l,r,root*2);
    else if(l>mid) query(l,r,root*2+1);
    else
    {
        query(l,mid,root*2);
        query(mid+1,r,root*2+1);
    }
}
// 更新主要是自顶向下找到该叶子节点，再自下向上回溯更新父亲节点对应的max
void update(int root)
{
    if(sgetree[root].l==index  && sgetree[root].r==index )
    {
        sgetree[root].v=grade;
        return ;
    }
    int mid=(sgetree[root].l+sgetree[root].r)/2;
    if(index<=mid)   update(root*2);
    else    update(root*2+1);
    sgetree[root].v=max(sgetree[root*2].v,sgetree[root*2+1].v);
}
// 递归建树
void build(int l,int r,int root)
{
    sgetree[root].l=l;
    sgetree[root].r=r;
    if(l==r)
    {
        sgetree[root].v=a[l];// a[right]一样
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,root*2);
    build(mid+1,r,root*2+1);
    sgetree[root].v=max(sgetree[root*2].v,sgetree[root*2+1].v);
}

int main(void)
{
    int n,m;
    while((scanf("%d%d",&n,&m))==2)
    {
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        build(1,n,1);
        while(m--)
        {
            ans=0;
            char str[2];
            scanf("%s",str);
            if(strcmp(str,"U")==0)
            {
                scanf("%d%d",&index,&grade);
                update(1);
            }
            else if(strcmp(str,"Q")==0)
            {
                scanf("%d%d",&l,&r);
                query(l,r,1);
                printf("%d\n",ans);
            }
        }
    }
}