士兵杀敌（RMQ入门题目）
#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; }/***************************http://acm.nyist.net/JudgeOnline/status.php?pid=119*******************************/