题目链接:
题目大意:
给你n个数,m次操作

Q L R 询问[L, R]的最大值
U L R 修改a[L]=R

思路:分块模板题

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int a[200010];
int mx[2000], mi[2000];
int Len, n, m;

int query(int L, int R)
{
    int bL=L/Len, bR=R/Len, Min=(1<<30), Max=0;

    if(bL==bR)//在同一块
    {
        for(int i=L;i<=R;i++)
        {
            Min=min(Min, a[i]);
            Max=max(Max, a[i]);
        }
    }
    else
    {
        for(int i=L; i<(bL+1)*Len; i++)//暴力左块
        {
            Min=min(Min, a[i]);
            Max=max(Max, a[i]);
        }

        for(int i=bL+1;i<bR; i++)//中间块
        {
            Min=min(Min, mi[i]);
            Max=max(Max, mx[i]);
        }

        for(int i=bR*Len; i<=R; i++)//暴力右块
        {
            Min=min(Min, a[i]);
            Max=max(Max, a[i]);
        }
    }

    return Max;
}

void revise(int i, int x)
{
    int si=i/Len;
    if(a[i]!=mi[si]&&a[i]!=mx[si])//不用整个重新维护
    {
        a[i]=x;
        mi[si]=min(a[i], mi[si]);
        mx[si]=max(a[i], mx[si]);
        return;
    }

    //全部重新维护
    a[i]=x;
    int Ln=(si+1)*Len;

    mi[si]=(1<<30), mx[si]=0;

    for(int i=si*Len; i<n&&i<Ln; i++)
    {
        mi[si]=min(a[i], mi[si]);
        mx[si]=max(a[i], mx[si]);
    }
}

int build(int n)
{
    Len=sqrt(n);//块大小
    for(int i=0;i<=n/Len;i++)
    {
        mi[i]=(1<<30);
        mx[i]=0;
    }

    for(int i=0;i<n;i++)
    {
        int si=i/Len;

        mx[si]=max(mx[si], a[i]);
        mi[si]=min(mi[si], a[i]);
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        build(n);

        while(m--)
        {
            char k[10];
            int L, R;

            scanf("%s%d%d",k,&L,&R);
            if(k[0]=='Q')
            {
                printf("%d\n", query(L-1, R-1));//下标从0开始
            }
            else
            {
                revise(L-1, R);
            }
        }
    }

    return 0;
}