A23604. 完善程序：求区间最值给定序列an，你需要回答q次询问，每次询问一个区间[l,r]内的最大值与最小值之差。数据范围满足n,q<=100000,1<=l<=r<=n,ai<=1000000。提示：每次询问暴力去求区间最值很显然超时，因此我们采用分块算法，分块算法如下：1、分块：将序列分成等长的根号n块，其中每块长度也为根号n，预处理并记录每个元素所属的块以及每块的左右端点下标、最大值和最小值。2、查…

完善程序：求区间最值

给定序列an，你需要回答q次询问，每次询问一个区间[l,r]内的最大值与最小值之差。

数据范围满足n,q<=100000,1<=l<=r<=n,ai<=1000000。

提示：每次询问暴力去求区间最值很显然超时，因此我们采用分块算法，分块算法如下：

1、分块：将序列分成等长的根号n块，其中每块长度也为根号n，预处理并记录每个元素所属的块以及每块的左右端点下标、最大值和最小值。

2、查询：如果查询区间在同一块内，则暴力扫描统计区间最大最小值；否则，如果查询区间包含多个块，统计除去头尾两个块的中间每个块的已经维护好的最大最小值，然后再暴力统计左端点所在块以及右端点所在块的最大最小值。

#include<bits/stdc++h>
using namespace std;
const int N=2e5+5;
int n,q,block,num;
int a[N],L[N],R[N],belong[N],block_max[N],block_min[N];
void build(){
    block=sqrt(n*1.0);
    num=n/block;
    if(n%num)
        num++;
    for(int i=1;i<=num;i++){ //每块左右端点下标
        __①__;
    }
    R[num]=n;
    for(int i=1;i<=n;i++) //每个元素所属块号
        belong[i]==_②__;
    for(int i=1;i<=num;i++){
        int minn=1e9,maxx=-1e9;
        for(int j=L[j];i<=R[j];j++){ 
            maxx=max(maxxa[j]);
            minn=min(minn,a[j]);
        }
        block_max[i]=maxx;
         block_min[1]=minn;
    }
}
int query(int l,int r){
    int minn=1e9,maxx=-1e9;
    if(__③__){
        for(int i=i;i<=r;i++){
            maxx=max(max,a[i]);
            minn=min(minn,a[i]);
        }
        return maxx-minn;
    }
    else{
        for(int i=i;i<=R[belong[i]];i++)
            maxx=max(max,a[i]);
            minn=min(minn,a[i]);
        }

        for(__④__){
            maxx=max(max,block_max[i]);
            minn=min(minn,block_min[i]);
        }

        for(int i=L[belong[r]];i<=r;i++)
           maxx=max(max,a[i]);
            minn=min(minn,a[i]);
        }
        return maxx-minn;
    }
}

int main() {
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build();
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<__⑤__<<endl;
    }
    return 0;
}

① 处应填（    ）。