【HYSBZ】1588 营业额统计

数据有两组漏了一个数，所以在读入之前要先赋值为0。
 1 #include<cstdio>
 2 #include<algorithm>
 3 #define MAXN 100010
 4 #define INF 0x7FFFFFFF
 5 using namespace std;
 6 struct SpalyTree {
 7     int size, root;
 8     int next[MAXN][2], pre[MAXN], key[MAXN];
 9     void Init() {
10         size = root = 0;
11     }
12     void NewNode(int &rt, int father, int val) {
13         rt = ++size;
14         next[rt][0] = next[rt][1] = 0;
15         pre[rt] = father;
16         key[rt] = val;
17     }
18     void Rotate(int x, int kind) {
19         int y = pre[x];
20         pre[next[x][kind]] = y;
21         next[y][!kind] = next[x][kind];
22         if (pre[y])
23             next[pre[y]][next[pre[y]][1] == y] = x;
24         pre[x] = pre[y];
25         next[x][kind] = y;
26         pre[y] = x;
27     }
28     void Splay(int x, int goal) {
29         while (pre[x] != goal) {
30             if (next[pre[x]][0] == x)
31                 Rotate(x, 1);
32             else
33                 Rotate(x, 0);
34         }
35         if (!goal)
36             root = x;
37     }
38     bool Insert(int k) {
39         int x, y;
40         for (x = root; next[x][k > key[x]]; x = next[x][k > key[x]]) {
41             if (k == key[x]) {
42                 Splay(x, 0);
43                 return false;
44             }
45         }
46         NewNode(next[x][k > key[x]], x, k);
47         Splay(next[x][k > key[x]], 0);
48         return true;
49     }
50     int GetPre() {
51         int x = next[root][0];
52         if (x) {
53             while (next[x][1])
54                 x = next[x][1];
55             return key[x];
56         }
57         return INF;
58     }
59     int GetNext() {
60         int x = next[root][1];
61         if (x) {
62             while (next[x][0])
63                 x = next[x][0];
64             return key[x];
65         }
66         return INF;
67     }
68 };
69 SpalyTree tree;
70 int main() {
71     int n, ans, x, a, b;
72     while (~scanf("%d%d", &n, &ans)) {
73         tree.Init();
74         tree.NewNode(tree.root, 0, ans);
75         while (--n) {
76             x = 0;
77             scanf("%d", &x);
78             if (tree.Insert(x)) {
79                 a = tree.GetPre();
80                 if (a < INF)
81                     a = x - a;
82                 b = tree.GetNext();
83                 if (b < INF)
84                     b -= x;
85                 ans += min(a, b);
86             }
87         }
88         printf("%d\n", ans);
89     }
90     return 0;
91 }