[HNOI2004]宠物收养所

Doubi Gao3 posted @ 2014年9月12日 21:36 in DataStructure with tags Splay , 986 阅读

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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter