题目链接：
算法：Splay
刚开始看到这题，就注意到特征abs了，并且数据n<=80000显然不能暴力，只能用nlgn的做法，综合起来，似乎只有一个答案：Splay。
将每次插入的点splay到树根，然后找到它的前驱和后继，再取它的绝对值即可，我们记作_abs。那么答案就为sum{_absi}，其中i为领养的人的数量，可以看为宠物的数量。
要注意的：
下面放上代码：
|
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 |
#include <cstdio>#include <cmath>using
namespace
std;#define NEW(d) new Splay(d)int
n, ans;struct
Splay { Splay* ch[2]; int
key; Splay(int
d = 0) : key(d) { ch[0] = ch[1] = NULL; } int
cmp(int
d) { if(d == key) return
-1; return
key > d ? 0 : 1; }}*root[2] = {NULL, NULL}; //两棵树int
who; //用来标志哪棵树正在操作typedef
Splay* tree;void
rot(tree& rt, int
d) { tree k = rt-> ch[d^1]; rt-> ch[d^1] = k-> ch[d]; k-> ch[d] = rt; rt = k;}void
splay(tree& rt, int
d) { if(rt == NULL) return; int
k = rt-> cmp(d); if(k != -1) { tree p = rt-> ch[k]; if(p != NULL) { int
k2 = p-> cmp(d); if(k2 != -1) { splay(p-> ch[k2], d); if(k == k2) rot(rt, k^1); else
rot(rt-> ch[k], k); } } rot(rt, k^1); }}//d = 0 : 前驱, d = 1 : 后继tree ps(tree rt, int
d) { rt = rt-> ch[d]; if(rt == NULL) return
NULL; while(rt-> ch[d^1] != NULL) rt = rt-> ch[d^1]; return
rt;}void
insert(tree& rt, int
d) { if(rt == NULL) { rt = NEW(d); splay(root[who], d); } else
{ if(rt-> key > d) insert(rt-> ch[0], d); else
insert(rt-> ch[1], d); }}void
del(tree& rt) { //这里我们不需要传递删除的点，因为删除的都是根 tree t; if(rt-> ch[0] == NULL) t = rt-> ch[1]; else
{ t = rt-> ch[0]; splay(t, ps(rt, 0)-> key); t-> ch[1] = rt-> ch[1]; } delete
rt; rt = t;}void
init(int
key, int
d) { //如果没有宠物或没有顾客了，先插入到对应的树 if(root[d^1] == NULL) { who = d; insert(root[who], key); return; } who = d^1; //操作变为另一棵树 insert(root[who], key); //将参数插入到根 tree succ = ps(root[who], 0), pred = ps(root[who], 1); int
l = 0, r = 0; if(succ != NULL) l = root[who]-> key - succ-> key; if(pred != NULL) r = pred-> key - root[who]-> key; //删除根 del(root[who]); //维护答案，并且删除对应的宠物或人 if(succ != NULL && (pred == NULL || l <= r)) { ans = (ans + l) % 1000000; splay(root[who], succ-> key); del(root[who]); } else
if(pred != NULL && (succ == NULL || r < l)) { ans = (ans + r) % 1000000; splay(root[who], pred-> key); del(root[who]); }}int
main() { scanf("%d", &n); int
c, b; while(~scanf("%d%d", &c, &b)) init(b, c); printf("%d", ans); return
0;} |
原文：http://www.cnblogs.com/iwtwiioi/p/3537130.html