传送门

描述

For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

输入

Line 1: Two space-separated integers, N and Q.

Lines 2.. N+1: Line i+1 contains a single integer that is the height of cow i

Lines N+2.. N+ Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

输出

Lines 1.. Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

样例

• 输入
  6 3
  1
  7
  3
  4
  2
  5
  1 5
  4 6
  2 2
• 输出
  6
  3
  0

思路

• 题意：给n个数和m次询问，每次询问给l和r，求区间[l,r]中最大值和最小值的差值。
• st[i][j]表示区间[i,i+2^j-1]内的最值。
• 以最大值为例，st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1])。
• 询问区间[l,r]时，取区间[l,l+(1<<k)]和[r-(1<<k)+1][r]，其中k=log(r-l+1.0)/log(2.0)，这样两个区间必有交集，则两个区间的最大值的最大值就一定是[l,r]的最大值。
• st表构造O(nlgn)，查找O(1)。当需要多次查找区间最值，不需要进行修改操作时，st表比线段树、树状数组更好用。

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long int using namespace std; const int MAX=0x7fffffff; const int MIN=-0x7fffffff; const int INF=0x3f3f3f3f; const int Mod=1e9+7; const int maxn=50007; int st1[maxn][20],st2[maxn][20]; int n,m,l,r; void Rmq(){
            for(int j=1;(1<
              
               <=n;j++) //外层j，稍加推导即可理解 for(int i=1;i+(1<
               
                <=n;i++){ //st[i][j]包含区间 [i,i+2^j-1] st1[i][j]=max(st1[i][j-1],st1[i+(1<<(j-1))][j-1]); st2[i][j]=min(st2[i][j-1],st2[i+(1<<(j-1))][j-1]); } } int Find(int l,int r){ int k=log(double(r-l+1))/log(2.0); int ans1=max(st1[l][k],st1[r-(1<