题目描述

在N（1<=N<=100000）个数A1…An组成的序列上进行M(1<=M<=100000)次操作，操作有两种：
(1)1 x y：表示修改A[x]为y；
(1)2 x y：询问x到y之间的最大值。

思路

用线段树记录一个max表示当前区间的最大值就可以了

#include 
#define maxn 500000
#define max(x,y) x>y?x:y
#define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int k=0;
int make(int p,int l,int r)
{
    int m=(l+r)>>1;
    if (l==r)
    {
        k++;
        t[p].max=a[k];
        return 0;
    }
    make(p<<1,l,m);
    make(p<<1|1,m+1,r);
    t[p].max=max(t[p<<1].max,t[p<<1|1].max);
}
int insert(int p,int l,int r,int x,int k)
{
    int m=(l+r)>>1;
    if (l==r)
    {
        t[p].max=k;
        return 0;
    }
    if (x<=m) insert(p<<1,l,m,x,k);
    else insert(p<<1|1,m+1,r,x,k);
    t[p].max=max(t[p<<1].max,t[p<<1|1].max);
}
int find(int p,int l,int r,int x,int y)
{
    int m=(l+r)>>1;
    if (l==x&&r==y)
        return t[p].max;
    if (y<=m) return find(p<<1,l,m,x,y);
    else if (x>m) return find(p<<1|1,m+1,r,x,y);
    else return max(find(p<<1,l,m,x,m),find(p<<1|1,m+1,r,m+1,y));
}
int main()
{
    int n=read(),m;
    for (int i=1;i<=n;i++)
        a[i]=read();
    make(1,1,n);
    m=read();

    for (int i=1;i<=m;i++)
    {

        int z=read(),x=read(),y=read();
        if (z==1)
            insert(1,1,n,x,y);

        else printf("%d\n",find(1,1,n,x,y));
    }
}