其实就是先用dp求出各个区间的最大最小值，然后查询的时候就O(1)了，不过用的二进制移位法，所以dp可以达到O(nlogn）速度……#include <iostream>#include <cstdio>#include <fstream>#include <algorithm>#include <cmath>#include <deque>#include <vector>#include <list>#include <queue>#include <string>#include <cstring>#include <map>#include <stack>#include <set>#define PI acos(-1.0)#define mem(a,b) memset(a,b,sizeof(a))#define sca(a) scanf("%d",&a)#define sc(a,b) scanf("%d%d",&a,&b)#define pri(a) printf("%dn",a)#define lson i<<1,l,mid#define rson i<<1|1,mid+1,r#define MM 100004#define MN 1008#define INF 100000007#define eps 1e-7using namespace std;typedef long long LL;typedef unsigned long long ULL;int a[MM];int stTableMin[MM][35],stTableMax[MM][35],preLog2[MM];void StPrepare(int n,int *a){ preLog2[1]=0; for(int i=2;i<=n;i++) { preLog2[i]=preLog2[i-1]; if((1<<preLog2[i]+1)==i) preLog2[i]++; } for(int i=n-1;i>=0;--i) { stTableMin[i][0]=stTableMax[i][0]=a[i]; for(int j=1;(i+(1<<j)-1)<n;++j) stTableMin[i][j]=min(stTableMin[i][j-1],stTableMin[i+(1<<j-1)][j-1]), stTableMax[i][j]=max(stTableMax[i][j-1],stTableMax[i+(1<<j-1)][j-1]); }}int queryMin(int l,int r){ int len=r-l+1,k=preLog2[len]; return min(stTableMin[l][k],stTableMin[r-(1<<k)+1][k]);}int queryMax(int l,int r){ int len=r-l+1,k=preLog2[len]; return max(stTableMax[l][k],stTableMax[r-(1<<k)+1][k]);}int main(){ int n,q,i,l,r; sc(n,q); for(i=0;i<n;i++) sca(a[i]); StPrepare(n,a); while(q--) { sc(l,r); l--,r--; pri(queryMax(l,r)-queryMin(l,r)); } return 0;}