分块算法-区间修改+区间最值

给定一个长度为n数列，现对这个序列有两种操作：
U L R X：将区间 [L, R] 每个数加X；

Q L R：查询从第L个数到第R个数得最大值和最小值。 所有的数都 <=1000
输入格式:
第一行给定一个整数n, m，表示有n个数。m个操作 以下接着一行，n个数。
再接下来m行每行一个操作。
输出格式:
对于每个查询输出一行最大值和最小值。
in:
5 3
1 2 3 4 5
U 1 2 3
U 5 5 -10
Q 1 5

out:
5 -5

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

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

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

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

        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]+add[bR]);
            Max=max(Max, a[i]+add[bR]);
        }
    }

    return make_pair(Max, Min);
}

void revise(int L, int R, int x)
{
    int bL=L/Len, bR=R/Len;

    if(bL==bR)//在同一块
    {
        mi[bL]=(1<<30), mx[bL]=-(1<<30);
        for(int i=bL*Len;i<(bL+1)*Len;i++)
        {
            if(i>=L&&i<=R)
            {
                a[i]+=x;
            }
            mi[bL]=min(mi[bL], a[i]+add[bL]);
            mx[bL]=max(mx[bL], a[i]+add[bL]);
        }
    }
    else
    {
        mi[bL]=(1<<30), mx[bL]=-(1<<30);
        for(int i=bL*Len; i<(bL+1)*Len; i++)//暴力左块
        {
            if(i>=L)
            {
                a[i]+=x;
            }
            mi[bL]=min(mi[bL], a[i]+add[bL]);
            mx[bL]=max(mx[bL], a[i]+add[bL]);
        }

        for(int i=bL+1;i<bR; i++)//中间块
        {
            add[i]+=x;
            mi[i]+=x;
            mx[i]+=x;
        }

        mi[bR]=(1<<30), mx[bR]=-(1<<30);
        for(int i=bR*Len; i<(bR+1)*Len; i++)//暴力右块
        {
            if(i<=R)
            {
                a[i]+=x;
            }
            mi[bR]=min(mi[bR], a[i]+add[bR]);
            mx[bR]=max(mx[bR], a[i]+add[bR]);
        }
    }
}

int build(int n)
{
    Len=sqrt(n);//块大小
    for(int i=0;i<=n/Len;i++)
    {
        mi[i]=(1<<30);
        mx[i]=-(1<<30);
        add[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, x;

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

    return 0;
}