HDu 1754 I Hate It(単点更新、区間最値)

1389 ワード

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define lson i<<1,l,m
#define rson i<<1|1,m+1,r
#define maxn 200005
int Max[maxn<<2];
void PushUp(int i)
{
    Max[i]=max(Max[i<<1],Max[i<<1|1]);
}
void build(int i,int l,int r)
{
    if(l==r) {scanf("%d",&Max[i]);getchar();return;}
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(i);
}
void update(int a,int b,int i,int l,int r)
{
    if(l==r) {Max[i]=b;return;}
    int m=(l+r)>>1;
    if(a<=m) update(a,b,lson);
    else update(a,b,rson);
    PushUp(i);
}
int query(int L,int R,int i,int l,int r)
{
    if(L<=l&&r<=R) return Max[i];
    int m=(l+r)>>1;
    int ans=0;
    if(L<=m) ans=max(ans,query(L,R,lson));
    if(R>m) ans=max(ans,query(L,R,rson));
    return ans;
}
int main()
{
    int m,n;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
            build(1,1,n);
            char s;
            while(m--)
            {
                int a,b;
                scanf("%c%d%d",&s,&a,&b);
                getchar();
                if(s=='Q') printf("%d
",query(a,b,1,1,n)); else if(s=='U') update(a,b,1,1,n); } } return 0; }