题目链接：http://www.wikioi.com/problem/1296/
算法：Splay
这是非常经典的一道题目，用Splay树来维护营业额，每天的最小波动值就等于 min{树根-树根的前驱, 树根的后继-树根)
所以用Splay来维护
PS: 本题数据有问题，所以当空行时，值为0
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106 |
#include <cstdio>using
namespace
std;#define F(rt) rt-> pa#define K(rt) rt-> key#define CH(rt, d) rt-> ch[d]#define C(rt, d) (K(rt) > d ? 0 : 1)#define NEW(d) new Splay(d)#define PRE(rt) F(rt) = CH(rt, 0) = CH(rt, 1) = nullint
n, ans;struct
Splay { Splay* ch[2], *pa; int
key; Splay(int
d = 0) : key(d) { ch[0] = ch[1] = pa = NULL; }};typedef
Splay* tree;tree null = new
Splay, root = null;void
rot(tree& rt, int
d) { tree k = CH(rt, d^1), u = F(rt); int
flag = CH(u, 1) == rt; CH(rt, d^1) = CH(k, d); if(CH(k, d) != null) F(CH(k, d)) = rt; CH(k, d) = rt; F(rt) = k; rt = k; F(rt) = u; if(u != null) CH(u, flag) = k;}void
splay(tree nod, tree& rt) { if(nod == null) return; tree pa = F(rt); while(F(nod) != pa) { if(F(nod) == rt) rot(rt, CH(rt, 0) == nod); else
{ int
d = CH(F(F(nod)), 0) == F(nod); int
d2 = CH(F(nod), 0) == nod; if(d == d2) { rot(F(F(nod)), d); rot(F(nod), d2); } else
{ rot(F(nod), d2); rot(F(nod), d); } } } rt = nod;}tree maxmin(tree rt, int
d) { if(rt == null) return
null; while(CH(rt, d) != null) rt = CH(rt, d); return
rt;}tree ps(tree rt, int
d) { if(rt == null) return
null; rt = CH(rt, d); return
maxmin(rt, d^1);}tree search(tree& rt, int
d) { tree t = rt; while(t != null && K(t) != d) t = CH(t, C(t, d)); splay(t, rt); return
t;}void
insert(tree& rt, int
d) { tree q = NULL, t = rt; while(t != null) q = t, t = CH(t, C(t, d)); t = NEW(d); PRE(t); if(q) F(t) = q, CH(q, C(q, d)) = t; else
rt = t; splay(t, rt);}void
del(tree& rt) { if(rt == null) return; tree t = rt; if(CH(t, 0) == null) t = CH(rt, 1); else
{ t = CH(rt, 0); splay(maxmin(t, 1), t); CH(t, 1) = CH(rt, 1); if(CH(rt, 1) != null) F(CH(rt, 1)) = t; } delete
rt; F(t) = null; rt = t;}void
init(int
key) { if(root == null) { root = NEW(key); PRE(root); ans += key; return; } insert(root, key); tree succ = ps(root, 0), pred = ps(root, 1); if(succ == null) { ans += K(pred) - K(root); splay(pred, root); return; } if(pred == null) { ans += K(root) - K(succ); splay(succ, root); return; } int
l = K(root) - K(succ), r = K(pred) - K(root); if(l <= r) { ans += l; splay(succ, root); } else
{ ans += r; splay(pred, root); }}int
main() { PRE(null); scanf("%d", &n); int
c; for(int
i = 0; i < n; ++i) { if(scanf("%d", &c) == EOF) c = 0; init(c); } //坑爹的读入 printf("%d\n", ans); return
0;} |
原文：http://www.cnblogs.com/iwtwiioi/p/3537901.html