一道RMQ板子题，分别维护最大值和最小值，不解释。
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4 #include<cmath>
5 #include<cstring>
6 #include<cstdlib>
7 #include<cctype>
8 #include<stack>
9 #include<queue>
10 #include<vector>
11 using namespace std;
12 #define enter puts("")
13 #define space putchar(' ')
14 #define Mem(a) memset(a, 0, sizeof(a))
15 typedef long long ll;
16 typedef double db;
17 const int INF = 0x3f3f3f3f;
18 const db eps =1e-8;
19 const int maxn = 5e4 + 5;
20 inline ll read()
21 {
22 ll ans = 0;
23 char ch = getchar(), last = ' ';
24 while(!isdigit(ch)) {last = ch; ch = getchar();}
25 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
26 if(last == '-') ans = -ans;
27 return ans;
28 }
29 inline void write(ll x)
30 {
31 if(x < 0) putchar('-'), x = -x;
32 if(x >= 10) write(x / 10);
33 putchar(x % 10 + '0');
34 }
35
36 int n, m, a[maxn];
37
38 int dp[maxn][20][2], b[maxn];
39 void RMQ()
40 {
41 for(int i = 1; i <= n; ++i) dp[i][0][0] = dp[i][0][1] = a[i];
42 for(int j = 1; (1 << j) <= n; ++j)
43 for(int i = 1; i + (1 << j) - 1 <= n; ++i)
44 {
45 dp[i][j][0] = max(dp[i][j - 1][0], dp[i + (1 << (j - 1))][j - 1][0]);
46 dp[i][j][1] = min(dp[i][j - 1][1], dp[i + (1 << (j - 1))][j - 1][1]);
47 }
48 int x = 0;
49 for(int i = 1; i <= n; ++i)
50 {
51 b[i] = x;
52 if((1 << (x + 1)) <= (i + 1)) x++;
53 }
54 }
55 int query(int L, int R, bool flag)
56 {
57 int k = b[R - L + 1];
58 if(flag) return min(dp[L][k][flag], dp[R - (1 << k) + 1][k][flag]); //应该是R - (1 << k) + 1,不是R - k + 1……
59 else return max(dp[L][k][flag], dp[R - (1 << k) + 1][k][flag]);
60 }
61
62
63 int main()
64 {
65 n = read(); m = read();
66 for(int i = 1; i <= n; ++i) a[i] = read();
67 RMQ();
68 for(int i = 1; i <= m; ++i)
69 {
70 int L = read(), R = read();
71 write(query(L, R, 0) - query(L, R, 1)); enter;
72 }
73 return 0;
74 }
View Code