題目鏈接：http://www.lightoj.com/volume_showproblem.php?problem=1093 話說(shuō)被題虐了好幾天了，一直沒(méi)有反虐，今天可算是找到一到簡(jiǎn)單題虐虐開(kāi)心開(kāi)心。 思路：維護(hù)的是區(qū)間最大值和區(qū)間最小值，然后對(duì)每一個(gè)長(zhǎng)度為d的區(qū)間進(jìn)行詢問(wèn)，最大值和最小值作差即可。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 100010;
11 int MAX[maxn << 2], MIN[maxn << 2];
12 void PushUp(int rt)
13 {
14 MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
15 MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]);
16 }
17 void build(int l, int r, int rt)
18 {
19 if (l == r)
20 {
21 scanf("%d", &MAX[rt]);
22 MIN[rt] = MAX[rt];
23 return;
24 }
25 int m = (l + r) >> 1;
26 build(lson);
27 build(rson);
28 PushUp(rt);
29 }
30 int queryd(int ll, int rr, int l, int r, int rt)
31 {
32 if (ll <= l && rr >= r) return MAX[rt];
33 int m = (l + r) >> 1;
34 int ret = 0;
35 if (ll <= m) ret = max(ret, queryd(ll, rr, lson));
36 if (rr > m) ret = max(ret, queryd(ll, rr, rson));
37 return ret;
38 }
39 int queryx(int ll, int rr, int l, int r, int rt)
40 {
41 if (ll <= l && rr >= r) return MIN[rt];
42 int m = (l + r) >> 1;
43 int ret = 100000010;
44 if (ll <= m) ret = min(ret, queryx(ll, rr, lson));
45 if (rr > m) ret = min(ret, queryx(ll, rr, rson));
46 return ret;
47 }
48 int main()
49 {
50 int t;
51 scanf("%d", &t);
52 for (int i = 1; i <= t; i++)
53 {
54 int n, d; scanf("%d%d", &n, &d);
55 build(1, n, 1);
56 int ans = 0;
57 for (int j = 1; j <= n - d + 1; j++)
58 {
59 int mx = queryd(j, j + d - 1, 1, n, 1);
60 int mn = queryx(j, j + d - 1, 1, n, 1);
61 int cnt = mx - mn;
62 ans = max(ans, cnt);
63 }
64 printf("Case %d: %d\n", i, ans);
65 }
66 return 0;
67
|