题意

求区间最大值减最小值的值

思路

其实就是一个存最大值的 ST 表加一个存最小值的 ST 表，然后相减就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5,LOG2N = 20;
int mx[N][LOG2N],mn[N][LOG2N],Log2[N];
int main(int argc, char **argv){
	int n,m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++){
		scanf("%d",mx[i]);
		mn[i][0] = mx[i][0];
	}
	for (int i = 2;i <= n;i++){
		Log2[i] = Log2[i >> 1] + 1;
	}
	for (int j = 1;j <= Log2[n];j++){
		for (int i = 1;i <= n - (1 << j) + 1;i++){
			mx[i][j] = max(mx[i][j - 1],mx[i + (1 << (j - 1))][j - 1]);
			mn[i][j] = min(mn[i][j - 1],mn[i + (1 << (j - 1))][j - 1]);
		}
	}
	while(m--){
		int l,r;
		scanf("%d%d",&l,&r);
		int k = Log2[r - l + 1];
		printf("%d\n",max(mx[l][k],mx[r - (1 << k) + 1][k]) - min(mn[l][k],mn[r - (1 << k) + 1][k]));
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int lg[50005];
int f1[50005][20];
int f2[50005][20];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	memset(f1,0,sizeof(f1));
	memset(f2,0x3f,sizeof(f2));
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		f1[i][0]=a;
		f2[i][0]=a;
	}
	lg[1]=0;
	for(int i=2;i<=n;i++){
		lg[i]=lg[i>>1]+1;
	}
	for(int j=1;j<=lg[n];j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			f1[i][j]=max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
		}		
	}
	for(int j=1;j<=lg[n];j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
		}		
	}	
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		int k=lg[r-l+1];
		cout<<max(f1[l][k],f1[r-(1<<k)+1][k])-min(f2[l][k],f2[r-(1<<k)+1][k])<<"\n";
	}
}