HNOI_2002 营业额统计（Splay)

此题可以用STL的multiset解决，也可以手打一棵伸展树（Splay）来求前驱与后驱。

使用multiset：

#include<iostream>
#include<set>
#include<algorithm>
#include<stdio.h>
using namespace std;

typedef long long LL;

multiset<LL> se;

/*
LL abs(LL a)
{
	return a > 0 ? a : -a;
}*/



int main()
{
	int n;
	scanf("%d", &n);
	LL a, ans = 0;
	multiset<LL>::iterator it, tmp1,tmp2;
	for (int i = 0; i < n; i++)
	{
		if (scanf("%lld", &a) == EOF) a = 0;
		se.insert(a);
		if (i == 0)
		{
			ans = a;
			continue;
		}
		it = se.find(a);
		tmp1 = tmp2 = it;
		if (it == se.begin())
		{
			it++;
			ans += (*it - a);
			continue;
		}
		tmp2++;
		if (tmp2 == se.end())
		{
			it--;
			ans += (a - *it);
			continue;
		}
		tmp1--;
		ans += min(a - *tmp1, *tmp2 - a);
		
	}
	printf("%lld
", ans);
	return 0;
}

使用Splay的代码：

#include<iostream>
#include<algorithm>
#define leftSon ch[0]
#define rightSon ch[1]
using namespace std;

struct node
{
	node *father, *ch[2];
	int key, sam;
	node(){ sam = 0; }
};

node *root;
node R;
bool flag = 1;

void Rotate(node *now, int c)
{
	node *y = now->father;
	y->ch[!c] = now->ch[c];
	if (now->ch[c] != NULL)
		now->ch[c]->father = y;
	now->father = y->father;
	if (y->father != NULL)
		if (y->father->ch[0] == y)
			y->father->ch[0] = now;
		else y->father->ch[1] = now;
		now->ch[c] = y, y->father = now;
		if (y == root) root = now;
}

void Splay(node *now, node *f)  // Splay
{
	for (; now->father != f;)
		if (now->father->father == f)
			if (now->father->ch[0] == now)
				Rotate(now, 1);
			else Rotate(now, 0);
		else
		{
			node *y = now->father, *z = y->father;
			if (z->ch[0] == y)
				if (y->ch[0] == now)
					Rotate(y, 1), Rotate(now, 1);
				else
					Rotate(now, 0), Rotate(now, 1);
			else if (y->ch[1] == now)
				Rotate(y, 0), Rotate(now, 0);
			else
				Rotate(now, 1), Rotate(now, 0);
		}
}

void ini()
{
	root = &R;
	root->father = root->ch[0] = root->ch[1] = NULL;
}

void Insert(int x, node *now, node *pre)
{
	if (now != NULL&&now->key == x){ now->sam++; return; }
	if (now == root&&flag)
	{
		now->key = x;
		now->rightSon = NULL;
		now->leftSon = NULL;
		now->father = pre;
		now->sam++;
		flag = 0;
		return;
	}
	if (now == NULL)
	{
		node *newNode;
		newNode = new node;
		newNode->key = x;
		newNode->rightSon = NULL;
		newNode->leftSon = NULL;
		newNode->father = pre;
		newNode->sam = 1;
		if (x > pre->key)
			pre->rightSon = newNode;
		else
			pre->leftSon = newNode;
		Splay(newNode, NULL);
		return;
	}
	if (x > now->key)
		Insert(x, now->rightSon, now);
	else
		Insert(x, now->leftSon, now);
}

node* find(int x, node *now)
{
	if (now == NULL)
		return NULL;
	if (now->key == x)
		return now;
	if (x < now->key)
		return find(x, now->ch[0]);
	else
		return find(x, now->ch[1]);
	return NULL;
}

node* searchMin(node *now)
{
	if (now == NULL)
		return NULL;
	if (now->leftSon == NULL)
		return now;
	searchMin(now->leftSon);
}

node* searchMax(node *now)
{
	if (now == NULL)
		return NULL;
	if (now->rightSon == NULL)
		return now;
	searchMax(now->rightSon);
}


void Delete(int x)
{
	node *now = find(x, root);
	if (now == NULL)
		return;
	if (now->key == x)
	{
		if (now->leftSon == NULL&&now->rightSon == NULL)
		{
			if (now->father->leftSon == now)
				now->father->leftSon = NULL;
			else
				now->father->rightSon = NULL;
			return;
		}
		if (now->leftSon == NULL&&now->rightSon != NULL)
		{
			if (now->father->leftSon == now)
				now->father->leftSon = now->rightSon;
			else
				now->father->rightSon = now->rightSon;
			now->rightSon->father = now->father;
			return;
		}
		if (now->leftSon != NULL&&now->rightSon == NULL)
		{
			if (now->father->leftSon == now)
				now->father->leftSon = now->leftSon;
			else
				now->father->rightSon = now->leftSon;
			now->leftSon->father = now->father;
			return;
		}
		node *tmp = searchMin(now->rightSon);
		now->key = tmp->key;
		now->sam = tmp->sam;
		if (tmp->father->leftSon == tmp)
			tmp->father->leftSon = NULL;
		else
			tmp->father->rightSon = NULL;
		return;
	}
}

void middleTravel(node *now)
{
	if (now == NULL)
		return;
	middleTravel(now->leftSon);
	for (int i = 0; i < (now->sam); i++)
		cout << now->key << " ";
	middleTravel(now->rightSon);
}



int main()
{
	ini();
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		int a;
		if (!(cin >> a))a = 0;
		if (i == 0)
		{
			ans = a;
			Insert(a, root, NULL);
			continue;
		}
		node *tmp = find(a, root);
		if (tmp != NULL)
		{
			Insert(a, root, NULL);
			continue;
		}
		Insert(a, root, NULL);
		tmp = find(a, root);
		node *pre = searchMax(tmp->ch[0]);
		node *nex = searchMin(tmp->ch[1]);
		if (pre == NULL&&nex != NULL)
			ans += nex->key - a;
		else if (pre != NULL&&nex == NULL)
			ans += a - pre->key;
		else if (pre != NULL&&nex != NULL)
			ans += min(a - pre->key, nex->key - a);
	}
	cout << ans << endl;
	return 0;
}