treap 树
本题要点：
1、建立两棵 treap 树， 一棵用来存 宠物，一棵树用来存 顾客。 题目给出的所有的顾客值和宠物值都不一样。
这样结构体 Treap 只需要 多一个 size 来就来子树的节点总数
2、套用 treap 树 的模板，写好 以下函数。 因为是两棵树，需要传参数的引用。
int New(int val, Treap* a, int& tot)void update(int p, Treap* a)void Build(Treap* a, int& tot, int& root)void zig(int &p, Treap* a) //右旋转void zag(int &p, Treap* a) //左旋void Insert(int &p, int val, Treap* a, int& tot)int GetPre(int val, Treap* a, int root)int GetNext(int val, Treap* a, int root)void Remove(int &p, int val, Treap* a)
3、如果新来了宠物 val ，那么判断顾客的 树是否为空，
如果顾客为空，把 val 插入到 宠物的 treap树;
否则，从顾客树中查找前驱 pre， 后继 nxt， 判断差值，看看选哪个。选了再删除。 还有，这里优先选择前驱。
如果新来的是 顾客 val, 同理操作。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int MaxN = 8e4 + 10, INF = 0x3fffffff, mod = 1000000;
int n, tot1, tot2, root1, root2;struct Treap
{
int l, r;int val, dat;int size; // 子树的节点总数
}client[MaxN], pet[MaxN];int New(int val, Treap* a, int& tot)
{
a[++tot].val = val;a[tot].dat = rand();a[tot].size = 1;return tot;
}void update(int p, Treap* a)
{
a[p].size = a[a[p].l].size + a[a[p].r].size + 1;
}void Build(Treap* a, int& tot, int& root)
{
New(-INF, a, tot), New(INF, a, tot);root = 1, a[1].r = 2;update(root, a);
}void zig(int &p, Treap* a) //右旋转
{
int q = a[p].l;a[p].l = a[q].r, a[q].r = p, p = q;update(a[p].r, a), update(p, a);
}void zag(int &p, Treap* a) //左旋
{
int q = a[p].r;a[p].r = a[q].l, a[q].l = p, p = q;update(a[p].l, a), update(p, a);
}void Insert(int &p, int val, Treap* a, int& tot)
{
if(0 == p){
p = New(val, a, tot);return;}if(val < a[p].val){
Insert(a[p].l, val, a, tot);if(a[p].dat < a[a[p].l].dat) zig(p, a); //不满足堆的条件，右旋}else{
Insert(a[p].r, val, a, tot);if(a[p].dat < a[a[p].r].dat) zag(p, a);}update(p, a);
}int GetPre(int val, Treap* a, int root)
{
int ans = 1; //a[1].val = -INF;int p = root;while(p){
if(val == a[p].val){
if(a[p].l > 0){
p = a[p].l;while(a[p].r > 0)p = a[p].r; //左子树一直往右走ans = p;}break;}if(a[p].val < val && a[p].val > a[ans].val) ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}int GetNext(int val, Treap* a, int root)
{
int ans = 2; int p = root;while(p){
if(val == a[p].val){
if(a[p].r > 0){
p = a[p].r;while(a[p].l > 0)p = a[p].l; //右子树一直往左走ans = p;}break;}if(a[p].val > val && a[p].val < a[ans].val)ans = p;p = val < a[p].val ? a[p].l : a[p].r;}return a[ans].val;
}void Remove(int &p, int val, Treap* a)
{
if(0 == p) return;if(val == a[p].val) //检查到val{
if(a[p].l || a[p].r){
if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat){
zig(p, a);Remove(a[p].r, val, a);}else{
zag(p, a);Remove(a[p].l, val, a);}update(p, a);}else{
a[p].size = 0;update(p, a);p = 0; //叶子节点，直接删除}return;}val < a[p].val ? Remove(a[p].l, val, a) : Remove(a[p].r, val, a);update(p, a);
}int main()
{
Build(pet, tot1, root1);Build(client, tot2, root2);int x, y, ans = 0, pre, nxt;scanf("%d", &n);for(int i = 0; i < n; ++i){
scanf("%d%d", &x, &y);if(0 == x) // 宠物{
if(client[root2].size == 2){
Insert(root1, y, pet, tot1); }else if(client[root2].size > 2){
pre = GetPre(y, client, root2); nxt = GetNext(y, client, root2);if(abs(y - nxt) < abs(y - pre)){
ans = (ans + abs(y - nxt)) % mod;Remove(root2, nxt, client);}else{
ans = (ans + abs(y - pre)) % mod;Remove(root2, pre, client);}}}else{
if(pet[root1].size == 2){
Insert(root2, y, client, tot2); }else if(pet[root1].size > 2){
pre = GetPre(y, pet, root1); nxt = GetNext(y, pet, root1);if(abs(y - nxt) < abs(y - pre)){
ans = (ans + abs(y - nxt)) % mod;Remove(root1, nxt, pet);}else{
ans = (ans + abs(y - pre)) % mod;Remove(root1, pre, pet);}}}}printf("%d\n", ans);return 0;
}/* 5 0 2 0 4 1 3 1 2 1 5 *//* 3 */