HDU 1754——I Hate It(線分木の単点修正)

基礎テンプレートの問題

<span style="font-size:18px;"><strong>#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define M 200001
#define ls(x) x<<1
#define rs(x) x<<1|1
#define inf 0x3f3f3f3f

using namespace std;
int n,m,a[M];
struct node
{
    int l,r,maxx;
}tre[M*4];

void push_up(int rt)
{
    tre[rt].maxx=max(tre[ls(rt)].maxx,tre[rs(rt)].maxx);
}

void build(int rt,int l,int r)
{
    tre[rt].l=l;
    tre[rt].r=r;
    if(l==r){
        tre[rt].maxx=a[l];return;
    }
    int m=(l+r)>>1;
    build(ls(rt),l,m);
    build(rs(rt),m+1,r);
    push_up(rt);
}

void add(int rt,int p,int v)
{
    if(tre[rt].l==tre[rt].r){
        tre[rt].maxx=v;
        return ;
    }
    int m=(tre[rt].l+tre[rt].r)>>1;
    if(p<=m) add(ls(rt),p,v);
    else add(rs(rt),p,v);
    push_up(rt);
}

int Query(int rt,int i,int j)
{
    if(i<=tre[rt].l&&tre[rt].r<=j) return tre[rt].maxx;
    int maxx=0;
    int m=(tre[rt].l+tre[rt].r)>>1;
    if(i<=m) maxx=max(maxx,Query(ls(rt),i,j));
    if(m<j) maxx=max(maxx,Query(rs(rt),i,j));
    return maxx;
}
int main()
{
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        char str[10];
        int i,j;
        while(m--){
            scanf("%s %d %d",str,&i,&j);
            if(str[0]=='Q'){
                printf("%d
",Query(1,i,j));
            }
            if(str[0]=='U'){
                add(1,i,j);
            }
        }
    }
    return 0;
}</strong></span>