Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:Splay模板测试,比Avl快,看来是Avl写傻逼勒。

Posted by GZHU1006100106 at 2014-04-07 17:56:38 on Problem 3481 and last updated at 2014-04-07 18:02:41
In Reply To:Avl模板测试(我怎么觉得AVL比SBT好写……错觉么) Posted by:GZHU1006100106 at 2014-04-07 16:36:38
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5+10;

template<class T> struct Splay {
	struct Node {
		Node *father, *son[2];
		T data;
		int side() {return father->son[1] == this;}
		Node *setSon(int vane, Node *orphan) {
			son[vane] = orphan;
			if (orphan) orphan->father = this;
			return this;
		}
		Node *spin() {
			Node *x = father;
			int vane = side();
			father = father->father;
			if (father) father->son[x->side()] = this;
			Node *y = son[!vane];
			setSon(!vane, x);
			x->setSon(vane, y);
			return this;
		}
		Node *fine(Node *sky = 0) {
			for ( ; father != sky; spin())
				if (father->father != sky)
					if (side() != father->side()) spin();
					else father->spin();
			return this;
		}
		Node *end(int vane) {return son[vane]? son[vane]->end(vane): this;}
		Node *find(T &data) {
			Node *x = this;
			while (1) {
				int vane = x->data < data;
				if (x->data == data || !x->son[vane]) break;
				x = x->son[vane];
			}
			return x;
		}
		Node *leave() {
			if (father) father->son[side()] = 0;
			father = 0;
			return this;
		}
	};
	Node pool[N], *top, *root;
	int size;
	Splay(): top(pool), root(0), size(0) {}
	Node *make(T &data) {
		Node t = {0, {0}, data};
		return &(*top++ = t);
	}
	void add(T &data) {
		Node *x = make(data);
		if (root) {
			root = root->find(data);
			root->setSon(root->data < data, x);
		}
		root = x->fine();
		size++;
	}
	T &find(T &data) {
		if (!root) return T();
		root = root->find(data);
		return root->fine()->data;
	}
	void remove(T &data) {
		root = root->find(data)->fine();
		if (root->data == data) {
			if (size == 1) root = 0;
			else {
				int vane = root->son[1] != 0;
				root->son[vane]->end(!vane)->fine(root);
				root->son[vane]->setSon(!vane, root->son[vane]);
				root = root->son[vane];
				root->leave();
			}
			size--;
		}
	}
	T &end(int vane) {return root->end(vane)->data;}
};

struct Client {
	int id, p;
	void input() {scanf("%d%d", &id, &p);}
	friend bool operator < (const Client &lhs, const Client &rhs) {
		return lhs.p < rhs.p;
	}
	friend bool operator == (const Client &lhs, const Client &rhs) {
		return lhs.p == rhs.p;
	}
};

Splay<Client> zkl;

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
	int op;
	while (scanf("%d", &op), op) {
		if (op == 1) {
			Client t;
			t.input();
			zkl.add(t);
		} else {
			if (!zkl.size) {
				puts("0");
			} else {
				Client ret = zkl.end(op == 2);
				printf("%d\n", ret.id);
				zkl.remove(ret);
			}
		}
	}
  return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator