C++(g++ 7.5.0) 解法, 执行用时: 342ms, 内存消耗: 20904K, 提交时间: 2023-07-05 20:27:39

#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
const int N = 1000005, mod = 1000000007;
int f1[50005][50], f2[50005][50], x;
int main() {
    int n, q;
    cin >> n >>q;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        f1[i][0] = f2[i][0] = x;
    }
    for (int j = 1; 1 << j <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f1[i][j] = max(f1[i][j - 1], f1[i + (1 << j - 1)][j - 1]);
            f2[i][j] = min(f2[i][j - 1], f2[i + (1 << j - 1)][j - 1]);
        }
    }
    while (q--) {
        int a, b,m1,m2;
        cin >> a >> b;
        int k = log2(b - a + 1);
        m1 = max(f1[a][k], f1[b - (1 << k) + 1][k]);
        m2 = min(f2[a][k], f2[b - (1 << k) + 1][k]);
        cout << m1 - m2 << endl;
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 131ms, 内存消耗: 11412K, 提交时间: 2020-01-29 15:45:41

#include <bits/stdc++.h>
 
using namespace std;
 
int a[100005],st[100005][25],n,st1[100005][25];
 
void ans(int l,int r)
{
    int k = log(r-l+1)/log(2);
    int ans = max(st[l][k],st[r-(1<<k)+1][k]);
    int ans1 = min(st1[l][k],st1[r-(1<<k)+1][k]);
    printf("%d\n",ans-ans1);
}
int main()
{
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",a+i),st[i][0] = st1[i][0] = a[i];
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;(i+(1<<j-1))<=n;i++)
    {
        st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
		st1[i][j] = min(st1[i][j-1],st1[i+(1<<j-1)][j-1]);
	}
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
    	ans(l,r);
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 657ms, 内存消耗: 1520K, 提交时间: 2023-07-06 16:15:40

#include<bits/stdc++.h>
using namespace std;
const int N =5e4+10;
const int M =1e6+10;
int h[N];
int n,q;

int main(void)
{
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>h[i];
    
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        int mins = M;
        int maxs=-1;
        
        for (int i=a;i<=b;i++)
        {
            if (h[i]<mins) mins=h[i];
            if (h[i]>maxs) maxs=h[i];
        }
        cout<<maxs-mins<<endl;
    }
    
    return 0;
}