Posted on 2008-05-25 16:07
superman 阅读(322)
评论(0) 编辑 收藏 引用 所属分类:
POJ
1 /* Accepted 6888K 3141MS G++ 1416B */
2 #include <math.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int n, m;
8 int A[50000];
9 int MIN[50000][16];
10 int MAX[50000][16];
11
12 void init()
13 {
14 for(int i = 0; i < n; i++)
15 MIN[i][0] = MAX[i][0] = A[i];
16 for(int j = 1; 1 << j <= n; j++)
17 for(int i = 0; i + (1 << j) - 1 < n; i++)
18 {
19 if(MIN[i][j - 1] < MIN[i + (1 << (j - 1))][j - 1])
20 MIN[i][j] = MIN[i][j - 1];
21 else
22 MIN[i][j] = MIN[i + (1 << (j - 1))][j - 1];
23
24 if(MAX[i][j - 1] > MAX[i + (1 << (j - 1))][j - 1])
25 MAX[i][j] = MAX[i][j - 1];
26 else
27 MAX[i][j] = MAX[i + (1 << (j - 1))][j - 1];
28 }
29 }
30
31 int main()
32 {
33 scanf("%d %d", &n, &m);
34 for(int i = 0; i < n; i++)
35 scanf("%d", &A[i]);
36
37 //ST algorithm
38 init();
39
40 //deal with query
41 int s, t;
42 while(m--)
43 {
44 scanf("%d %d", &s, &t);
45 s--, t--;
46
47 int a, b, k = int(log(t - s + 1) / log(2));
48
49 if(MIN[s][k] < MIN[t - (1 << k) + 1][k])
50 a = MIN[s][k];
51 else
52 a = MIN[t - (1 << k) + 1][k];
53
54 if(MAX[s][k] > MAX[t - (1 << k) + 1][k])
55 b = MAX[s][k];
56 else
57 b = MAX[t - (1 << k) + 1][k];
58
59 cout << b - a << endl;
60 }
61
62 return 0;
63 }
64