1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 #define N 50010 7 #define INF 0x3f3f3f3f 8 int dpmin[N][20], dpmax[N][20], n; 9 10 void Init() {11     memset(dpmin, INF, sizeof(dpmin));12     for(int i = 1; i <= n; i++) { scanf("%d", &dpmin[i][0]); dpmax[i][0] = dpmin[i][0]; }13     int limit = (int)(log(n) / log(2));14     for(int j = 1; j <= limit; j++)15         for(int i = 1; i + (1 << j) - 1 <= n; i++)16             dpmin[i][j] = min(dpmin[i][j-1], dpmin[i+(1<<(j-1))][j-1]), dpmax[i][j] = max(dpmax[i][j-1], dpmax[i+(1<<(j-1))][j-1]);17 }18 19 int Query(int l, int r) {20     int k = (int)(log(r - l + 1) / log(2));21     return max(dpmax[l][k], dpmax[r-(1<<k)+1][k]) - min(dpmin[l][k], dpmin[r-(1<<k)+1][k]);22 }23 24 int main() {25     int q;26     while(~scanf("%d%d", &n, &q)) {27         Init();28         while(q--) {29             int l, r; scanf("%d%d", &l, &r);30             printf("%d\n", Query(l, r));31         }32     }33     return 0;34 }