题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1208
题意：
有一个宠物收养所，在接下来一段时间内会陆续有一些宠物进到店里，或是一些人来领养宠物。宠物和人的总数量为n。
t = 0代表宠物，t = 1代表人。
宠物和人分别有一个特点值a和b。有两种情况：
（1）店里全是宠物，这时进来一个人来领养宠物。那么他会领养走abs(a-b)最小的那只宠物（b = a - x or a + x）。
如果使得abs(a-b)最小的有不止一只宠物，那么b = a - x的那只会被领养走。
（2）店里全是等待的人。这事有一只宠物被送进店里，那么它会被abs(a-b)最小的那个人领养走（a = b - x or b + x）。
如果使得abs(a-b)最小的不只有一个人，那么宠物会被a = b - x的人领养走。
按照依次来到店里的顺序，给出a,b。
a = 0代表宠物，a = 1代表人。b为对应的特点值。
定义每一次领养的不满意度 = abs（宠物特点值 - 人的特点值）
问你所有不满意度之和 MOD 1000000。
题解：
Splay。
分析：
（1）在每一个时刻（除了正在领养），店里要么全是宠物，要么全是人，要么为空。
（2）在本题中，除了只能是人和宠物匹配这个特性，人和宠物是等价的，都可以在店里等待。
（3）有可能先进来一大堆宠物，再进来一大堆人。这时搜索树会退化成链，所以要用splay。
实现：
每输入一对a,b:
（1）如果店为空，那么将东西加入树中，并将树的类型改为a。
（2）如果进来一个同类，那么将当前东西加入树中。
（3）如果进来一个异类，那么找出对于这个异类的特点值的前驱pre与后继suc（类型均为pair<int,int>(dif,idx)）。
将被删除的东西为res = min(pre,suc)。
所以erase(res.second)，并更新答案ans = (ans + res.first) % MOD。
AC Code:
1 #include <iostream>
2 #include <stdio.h>
3 #include <string.h>
4 #define MAX_N 80005
5 #define MOD 1000000
6 #define INF 100000000
7
8 using namespace std;
9
10 int n,a,b;
11 int ans=0;
12 int type;
13 int siz=0;
14 int tot=0;
15 int root=-1;
16 int dat[MAX_N];
17 int par[MAX_N];
18 int lson[MAX_N];
19 int rson[MAX_N];
20
21 void rotate(int x,int type,int *lson,int *rson)
22 {
23 if(type==1) swap(lson,rson);
24 int y=par[x];
25 int z=par[y];
26 lson[y]=rson[x];
27 if(rson[x]!=-1) par[rson[x]]=y;
28 par[x]=z;
29 if(z!=-1)
30 {
31 if(lson[z]==y) lson[z]=x;
32 else rson[z]=x;
33 }
34 rson[x]=y;
35 par[y]=x;
36 }
37
38 void splay(int x,int act)
39 {
40 while(par[x]!=act)
41 {
42 int y=par[x];
43 int z=par[y];
44 if(z==act)
45 {
46 if(lson[y]==x) rotate(x,0,lson,rson);
47 else rotate(x,1,lson,rson);
48 }
49 else
50 {
51 if(lson[z]==y && lson[y]==x)
52 {
53 rotate(y,0,lson,rson);
54 rotate(x,0,lson,rson);
55 }
56 if(rson[z]==y && rson[y]==x)
57 {
58 rotate(y,1,lson,rson);
59 rotate(x,1,lson,rson);
60 }
61 if(rson[z]==y && lson[y]==x)
62 {
63 rotate(x,0,lson,rson);
64 rotate(x,1,lson,rson);
65 }
66 if(lson[z]==y && rson[y]==x)
67 {
68 rotate(x,1,lson,rson);
69 rotate(x,0,lson,rson);
70 }
71 }
72 }
73 if(act==-1) root=x;
74 }
75
76 int find(int val)
77 {
78 int now=root;
79 while(now!=-1)
80 {
81 if(val==dat[now]) return now;
82 if(val<dat[now]) now=lson[now];
83 if(val>dat[now]) now=rson[now];
84 }
85 return -1;
86 }
87
88 void new_node(int val,int p,int &kid)
89 {
90 dat[tot]=val;
91 par[tot]=p;
92 lson[tot]=-1;
93 rson[tot]=-1;
94 kid=tot;
95 splay(tot,-1);
96 tot++;
97 }
98
99 void insert(int val)
100 {
101 siz++;
102 if(root==-1)
103 {
104 int temp;
105 root=tot;
106 new_node(val,-1,temp);
107 return;
108 }
109 int now=root;
110 while(1)
111 {
112 if(val==dat[now]) return;
113 if(val<dat[now])
114 {
115 if(lson[now]==-1)
116 {
117 new_node(val,now,lson[now]);
118 return;
119 }
120 else now=lson[now];
121 }
122 if(val>dat[now])
123 {
124 if(rson[now]==-1)
125 {
126 new_node(val,now,rson[now]);
127 return;
128 }
129 else now=rson[now];
130 }
131 }
132 }
133
134 void erase(int x)
135 {
136 siz--;
137 splay(x,-1);
138 if(lson[x]==-1 && rson[x]==-1)
139 {
140 root=-1;
141 return;
142 }
143 if(lson[x]==-1)
144 {
145 root=rson[x];
146 par[rson[x]]=-1;
147 return;
148 }
149 if(rson[x]==-1)
150 {
151 root=lson[x];
152 par[lson[x]]=-1;
153 return;
154 }
155 int pre=lson[root];
156 while(rson[pre]!=-1) pre=rson[pre];
157 splay(pre,x);
158 par[pre]=-1;
159 rson[pre]=rson[x];
160 par[rson[x]]=pre;
161 root=pre;
162 }
163
164 pair<int,int> precursor(int val)
165 {
166 int now=root;
167 int pre=-1;
168 int dif=INF;
169 while(now!=-1)
170 {
171 if(dat[now]<val && val-dat[now]<dif)
172 {
173 pre=now;
174 dif=val-dat[now];
175 }
176 if(dat[now]>val) now=lson[now];
177 else now=rson[now];
178 }
179 return pair<int,int>(dif,pre);
180 }
181
182 pair<int,int> succeed(int val)
183 {
184 int now=root;
185 int suc=-1;
186 int dif=INF;
187 while(now!=-1)
188 {
189 if(dat[now]>val && dat[now]-val<dif)
190 {
191 suc=now;
192 dif=dat[now]-val;
193 }
194 if(dat[now]>val) now=lson[now];
195 else now=rson[now];
196 }
197 return pair<int,int>(dif,suc);
198 }
199
200 int main()
201 {
202 cin>>n;
203 for(int i=0;i<n;i++)
204 {
205 cin>>a>>b;
206 if(siz==0)
207 {
208 insert(b);
209 type=a;
210 }
211 else
212 {
213 if(a==type) insert(b);
214 else
215 {
216 pair<int,int> pre=precursor(b);
217 pair<int,int> suc=succeed(b);
218 pair<int,int> res=min(pre,suc);
219 erase(res.second);
220 ans=(ans+res.first)%MOD;
221 }
222 }
223 }
224 cout<<ans<<endl;
225 }