#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#define MAXN 100010#define Max(x,y) (x>y?x:y)#define Min(x,y) (x>y?y:x)using namespace std;int maxsum[MAXN][18],minsum[MAXN][18];///表示从第i个数起连续2^j个数中的最大值/最小值 void RMQ(int num) {for(int j=1; j<18; j++) {for(int i=1; i<=num; i++) {if(i+(1<<j)-1 <= num) {maxsum[i][j]=Max(maxsum[i][j-1], maxsum[i+(1<<(j-1))][j-1]);// printf("maxsum[%d][%d]=Max(maxsum[%d][%d], maxsum[%d][%d])\n", i, j, i, j-1, i+(1<<(j-1)), j-1);// printf("%d = max( %d , %d)\n", maxsum[i][j], maxsum[i][j-1], maxsum[i+(1<<(j-1))][j-1]);minsum[i][j]=Min(minsum[i][j-1], minsum[i+(1<<(j-1))][j-1]);}}} } int main() {int i, num, query;while(scanf("%d%d",&num, &query) != EOF) {for(i=1; i<=num; i++) {scanf("%d", &maxsum[i][0]);minsum[i][0] = maxsum[i][0];}RMQ(num);int st, en, maxl, minl;while(query–) {scanf("%d%d", &st, &en);int k=(int)((log(en-st+1))/log(2.0));maxl=Max(maxsum[st][k], maxsum[en-(1<<k)+1][k]);minl=Min(minsum[st][k], minsum[en-(1<<k)+1][k]);printf("%d\n",maxl-minl);}}return 0; }/***************************?pid=119*******************************/
，用开怀的笑容去迎接每一个黎明，
