学步园

题意：求一段区间内的最大值，和对原来的数组进行改变

做法：入门级的线段树...

#include <iostream>
#include <cstdio>
#include <cstring>
#define LMT 200002
#define left l,m,x<<1
#define right m+1,r,x<<1|1
using namespace std;
int smax[LMT<<2];
int max(int a,int b)
{
    return a>b?a:b;
}
void build(int l,int r,int x)
{
    if(l==r)
    {
        scanf("%d",&smax[x]);
        return;
    }
    int m=(l+r)>>1;
    build(left);
    build(right);
    smax[x]=max(smax[x<<1],smax[x<<1|1]);
}
void update(int pos,int key,int l,int r,int x)
{
    if(l==r)
    {
        smax[x]=key;
        return;
    }
    int m=(l+r)>>1;
    if(pos<=m)update(pos,key,left);
    if(pos>m)update(pos,key,right);
    smax[x]=max(smax[x<<1],smax[x<<1|1]);
}
int equery(int L,int R,int l,int r,int x)
{
    if(L<=l&&r<=R)return smax[x];
    int a=-1,b=-1,m=(l+r)>>1;
    if(L<=m)a=equery(L,R,left);
    if(R>m)b=equery(L,R,right);
    return max(a,b);
}
int main()
{
    char ord[3];
    int n,q;
    while(~scanf("%d%d",&n,&q))
    {
        build(1,n,1);
        while(q--)
        {
            int a,b;
            scanf("%s",ord);
            if(strcmp(ord,"Q")==0)
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",equery(a,b,1,n,1));
            }
            else
            {
                scanf("%d%d",&a,&b);
                update(a,b,1,n,1);
            }
        }
    }
    return 0;
}