Splay求前驱与后继，然后累加和即可。

书上的Splay求x的前驱与后继需要插入x之后才能求得前驱与后继。删除操作时把x与前驱或者后继删除即可。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;

typedef int Comparable;

struct Node
{
	Node *left, *right;
	int element;
	Node(int v=0, Node *lt=0, Node *rt=0):element(v),left(lt),right(rt) {}
};

Node *null = new Node();

void rotateWithLeftChild(Node *&t)
{
	Node *k = t->left;
	t->left = k->right;
	k->right = t;
	t = k;
}

void rotateWithRightChild(Node *&t)
{
	Node *k = t->right;
	t->right = k->left;
	k->left = t;
	t = k;
}

void splay(Node *&t, const Comparable &x)
{
	Node *leftTreeMax, *rightTreeMin;
	
	static Node head;
	
	head.left = head.right = null;
	
	leftTreeMax = rightTreeMin = &head;
	null->element = x;
	
	for(;;)
	{
		if(x < t->element)
		{
			if(x < t->left->element)
				rotateWithLeftChild(t);
			if(t->left == null) break;
			
			//Link Right
			rightTreeMin->left = t;
			rightTreeMin = t;
			t = t->left;
		}
		else if(x > t->element)
		{
			if(x > t->right->element)
				rotateWithRightChild(t);
			if(t->right == null) break;
			
			//Link left
			leftTreeMax->right = t;
			leftTreeMax = t;
			t = t->right;
		}
		else break;
	}
	
	leftTreeMax->right = t->left;
	rightTreeMin->left = t->right;
	
	t->left = head.right;
	t->right = head.left;
}

int insert(Node *&root, const Comparable &x)
{
	Node* newNode = new Node(x);
	
	if(root == null)
	{
		newNode->left = newNode->right = null;
		root = newNode;
		return 0;
	}
	
	splay(root, x);
	if(x < root->element)
	{
		newNode->left = root->left;
		newNode->right = root;
		root->left = null;
		root = newNode;
	}
	else if(x > root->element)
	{
		newNode->right = root->right;
		newNode->left = root;
		root->right = null;
		root = newNode;
	}
	else return -1;
	
	newNode = NULL;
	
	return 1;
}

void printTree(Node *o)
{
	if(o != null)
	{	
		printf("%d ", o->element);
		printTree(o->left);
		printTree(o->right);
	}
}

void remove(Node *&o, int x)
{
	splay(o, x);
	if(o->element != x) return ;
	
	Node *newTree;
	if(o->left == null)
		newTree = o->right;
	else
	{
		newTree = o->left;
		splay(newTree, x);
		newTree->right = o->right;
	}
	
	delete o;
	o = newTree;
}

Node *findMin(Node *o)
{
	if(o == null) return null;
	while(o->left != null)
		o = o->left;
	return o;
}

Node *findMax(Node *o)
{
	if(o == null) return null;
	while(o->right != null)
		o = o->right;
	return o;
}

Node *predecessor(Node *o, int x)
{
	splay(o, x);
	return findMax(o->left);
}

Node *successor(Node *o, int x)
{
	return findMin(o->right);
}

///////////////////////
int n;
const int INF = 0x3f3f3f3f;

void readint(int &x)
{
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	
	x = 0;
	while(isdigit(c))
	{
		x = x*10+c-'0';
		c = getchar();
	}
}

int main()
{
	while(~scanf("%d", &n))
	{
		Node *root = null; root->left = null; root->right = null;
		
		int ans = 0, flag = -1;
		for(int i = 1; i <= n; i++)
		{
			int cmd, x; scanf("%d%d", &cmd, &x);
			if(flag == -1)
			{
				insert(root, x);
				flag = cmd;
			}
			else if(flag == cmd)
			{
				insert(root, x);
			}
			else
			{
				int p = insert(root, x);
				if(p == -1)
				{
					remove(root, x);
				}
				else
				{
					Node *pre = predecessor(root, x);
					Node *next = successor(root, x);
					int t1 = pre != null? pre->element:INF;
					int t2 = next != null? next->element:INF;
					if(abs(t1-x) <= abs(t2-x))
					{
						ans = (ans+abs(t1-x))%1000000;
						remove(root, t1);
						remove(root, x);
					}
					else
					{
						ans = (ans+abs(t2-x))%1000000;
						remove(root, t2);
						remove(root, x);
					}
				}
				if(root == null) flag = -1;
			}
		}
		printf("%d\n", ans%1000000);
	}
	return 0;
}

                         Splay伸展树

Splay是二叉查找树，不是一颗平衡树，但可以通过自调整达到一种近似平衡的情况。Splay在连续M次操作中均摊时间复杂度是M*logn，其中n为节点的个数，M为操作的次数。Splay的操作与特点将在以下介绍。

• 当访问一个节点时，立即把当前访问的节点旋转到根节点，让访问（插入）的节点立马成为新的根节点。
• 旋转操作与AVL很像，有两种旋转，左旋、右旋。
• Splay操作有两种不同的实现方式。一种是自底向上的旋转，需要记录当前节点的父亲节点。另外一种是自顶向上的实现方式，不需要记录父亲节点。
• 由于Splay把当前访问的节点放在根节点，很容易求出当前节点的前驱与后继。
• Splay支持merge、split、findMin、findMax、predecessor、successor、insert、remove等操作。
• 在信息学竞赛中，Splay可以实现能实现线段树的所有的功能，即pushup、pushdown维护区间信息在Splay中用的很活，但Splay又支持快速的序列分离和合并，这是线段树做不到的。
• 验证自己手写的数据结构是否正确可以去OJ写一写用到该数据结构的题。

最近在学高级数据结构，AVL、BST、SPLAY、Treap、红黑树等，能够快速实现AVL、BST、SPLAY、Treap，以及会利用简单变形解决某些问题就达到要求了。

大学计算机专业的学生，数据结构书上的所有数据结构能够快速实现，对计算机理论不至于精通，但要熟悉，随便提出一个基础理论至少不陌生。高数、现代、概率论都要达到熟悉的地步。

Treap,顾名思义，Tree+Heap的简称，与BST不同，节点还附加了一个随机优先级来平衡树，所以又带有堆的性质，可以证明最坏的查找、删除效率为O(logn)，它可以做到set做不到的事，如快速求第K大值，以及求值x的名次，也被称作名次树。如果附加的优先级是固定的话，那么就成了笛卡尔树。