分块14ptsqt

#include<bits/stdc++.h>
using namespace std;
int a[50009];
int mx[50009],mn[50009],block_size;
int get(int i)
{
    return (i-1)/block_size+1;
}
int main()
{
    int n,q;
    cin>>n>>q;
    block_size=sqrt(n);
    memset(mn,0x7f,sizeof mn);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        int p=get(i);
        mx[p]=max(mx[p],a[i]);
        mn[p]=min(mn[p],a[i]);
        
    }
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        int start=get(l),end=get(r); //块编号
        int Mx=0,Mn=INT_MAX;
        int ed1,ed2;
        if(start<end)
        {
            ed1=min(start*block_size,r); //下标 第一个不完整块结尾
            for(int j=l;j<=ed1;j++)Mx=max(Mx,a[j]);
            for(int j=start;j<=end;j++)Mx=max(Mx,mx[j]);
            ed2=max(l+1,(end-1)*block_size+1); //第二个不完整块开始
            for(int j=ed2;j<=r;j++)Mx=max(Mx,a[j]);
        }
        else{for(int j=l;j<=r;j++)Mx=max(Mx,a[j]);}
        //cout<<ed1<<" | "<<ed2<<endl;
        
        if(start<end)
        {
            ed1=min(start*block_size,r); //下标 第一个不完整块结尾
            for(int j=l;j<=ed1;j++)Mn=min(Mn,a[j]);
            for(int j=start;j<=end;j++)Mn=min(Mn,mn[j]);
            ed2=max(l+1,(end-1)*block_size+1); //第二个不完整块开始
            for(int j=ed2;j<=r;j++)Mn=min(Mn,a[j]);
        }
        else{for(int j=l;j<=r;j++)Mn=min(Mn,a[j]);}
        cout<<Mx-Mn<<endl;
    }
}