题目链接：
算法：Splay
刚开始看到这题，就注意到特征abs了，并且数据n<=80000显然不能暴力，只能用nlgn的做法，综合起来，似乎只有一个答案：Splay。
将每次插入的点splay到树根，然后找到它的前驱和后继，再取它的绝对值即可，我们记作_abs。那么答案就为sum{_absi}，其中i为领养的人的数量，可以看为宠物的数量。
要注意的：
- 领养者将会领养特点值为a-b的那只宠物 和 特点值为a-b的那个领养者将成功领养该宠物 告诉我们要取前驱。
- 同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个。 告诉我们要建两棵Splay树来存剩下的人。
- 操作人的和操作动物的几乎一样。
下面放上代码：
|
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;
} |