学步园

hdoj 2871 

poj 3667 hotel套了个马甲 

线段树基本操作不用变,按分配内存先后分别标记每个内存块的编号,增加一个查找某点所属内存块的编号的函数

记录每个内存块的起始位置和结束位置，然后维护一颗BST，以起始编号为主键，求第k大即可

线段树+SBT

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>
#include <map>
#include <string>
#include <climits> 
#include <set>
#include <string> 
#include <sstream>
#include <utility>
#include <ctime>

using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::getline;
using std::make_pair;
using std::greater;

const int MAXN(50010);

struct ELE
{
	int key1, key2;
	ELE(int tk1 = 0, int tk2 = 0): key1(tk1), key2(tk2)
	{}

	friend bool operator < (const ELE &op1, const ELE &op2)
	{
		return op1.key1 < op2.key1;
	}
	friend bool operator > (const ELE &op1, const ELE &op2)
	{
		return op1.key1 > op2.key1;
	}
	friend bool operator >= (const ELE &op1, const ELE &op2)
	{
		return op1.key1 >= op2.key1;
	}
	friend bool operator == (const ELE &op1, const ELE &op2)
	{
		return op1.key1 == op2.key1;
	}
	friend ELE operator +(ELE op1, int op2)
	{
		op1.key1 += op2;
		return op1;
	}
};

template<typename T>
struct SBT
{
	struct NODE
	{
		T key;
		int size;
		NODE *left;
		NODE *right;
	};

	NODE pool[MAXN];
	NODE *root, *NIL, *rear;
	T tkey;
	void init()
	{
		NIL = pool;
		rear = pool+1;
		NIL->size = 0;
		NIL->left = NIL;
		NIL->right = NIL;
		root = NIL;
	}

	NODE *newnode(const T &value)
	{
		rear->key = value;
		rear->left = NIL;
		rear->right = NIL;
		rear->size = 1;
		return rear++;
	}
	
	void left_rotate(NODE *&sour)
	{
		NODE *temp = sour->right;
		sour->right = temp->left;
		temp->left = sour;
		temp->size = sour->size;
		sour->size = sour->left->size+sour->right->size+1;
		sour = temp;
	}

	void right_rotate(NODE *&sour)
	{
		NODE *temp = sour->left;
		sour->left = temp->right;
		temp->right = sour;
		temp->size = sour->size;
		sour->size = sour->left->size+sour->right->size+1;
		sour = temp;
	}

	void maintain(NODE *&sour, bool flag)
	{
		if(flag == false)
		{
			if(sour->left->left->size > sour->right->size)
			{
				right_rotate(sour);
			}
			else
				if(sour->left->right->size > sour->right->size)
				{
					left_rotate(sour->left);
					right_rotate(sour);
				}
				else
					return;
		}
		else
		{
			if(sour->right->right->size > sour->left->size)
			{
				left_rotate(sour);
			}
			else
				if(sour->right->left->size > sour->left->size)
				{
					right_rotate(sour->right);
					left_rotate(sour);
				}
				else
					return;
		}
		maintain(sour->right, true);
		maintain(sour->left, false);
		maintain(sour, true);
		maintain(sour, false);
	}
	
	void insert(const T &value)
	{
		tkey = value;
		insert_(root);
	}

	void insert_(NODE *&sour)
	{
		if(sour == NIL)
		{
			sour = newnode(tkey);
			return;
		}
		++sour->size;
		if(tkey < sour->key)
			insert_(sour->left);
		else
			insert_(sour->right);
		maintain(sour, tkey >= sour->key);
	}

	void erase(T value)
	{
		erase_(root, value);
	}

	T erase_(NODE *&sour, const T &value)
	{
		--sour->size;
		if(value == sour->key || (value < sour->key && sour->left == NIL) || (value > sour->key && sour->right == NIL))
		{
			T temp = sour->key;
			if(sour->left == NIL || sour->right == NIL)
				sour = sour->left-NIL+sour->right;
			else
				sour->key = erase_(sour->left, value+1);
			return temp;
		}

		if(value < sour->key)
			return erase_(sour->left, value);
		else
			return erase_(sour->right, value);
	}

	NODE *select(int r)
	{
		NODE *sour = root;
		while(sour != NIL && r != sour->left->size+1)
		{
			if(r <= sour->left->size)
				sour = sour->left;
			else
			{
				r -= sour->left->size+1;
				sour = sour->right;
			}
		}
		return sour;
	}
};

struct SEGMENT_TREE
{
	int cover[MAXN << 2], lsum[MAXN << 2], rsum[MAXN << 2], msum[MAXN << 2];
	inline int left_son(int root)
	{
		return root << 1;
	}

	inline int right_son(int root)
	{
		return (root << 1)|1;
	}

	void push_up(int root, int l1, int l2)
	{
		lsum[root] = lsum[left_son(root)];
		rsum[root] = rsum[right_son(root)];
		if(lsum[root] == l1)
			lsum[root] += lsum[right_son(root)];
		if(rsum[root] == l2)
			rsum[root] += rsum[left_son(root)];
		msum[root] = max(rsum[left_son(root)]+lsum[right_son(root)], max(msum[left_son(root)], msum[right_son(root)]));
	}

	void push_down(int root, int l1, int l2)
	{
		if(cover[root] != -1)
		{
			cover[left_son(root)] = cover[right_son(root)] = cover[root];
			lsum[left_son(root)] = rsum[left_son(root)] = msum[left_son(root)] = cover[root]? 0: l1;
			lsum[right_son(root)] = rsum[right_son(root)] = msum[right_son(root)] = cover[root]? 0: l2;
			cover[root] = -1;
		}
	}

	void build_tree(int l, int r, int root)
	{
		cover[root] = -1;
		lsum[root] = rsum[root] = msum[root] = r-l+1;
		if(l == r)
			return;
		int m = (l+r) >> 1;
		build_tree(l, m, left_son(root));
		build_tree(m+1, r, right_son(root));
	}
	
	int allocate(int op, int l, int r, int root)
	{
		if(l == r)
			return l;
		int m = (l+r) >> 1;
		push_down(root, m-l+1, r-m);
		if(op <= msum[left_son(root)])
			return allocate(op, l, m, left_son(root));
		else
			if(op <= rsum[left_son(root)]+lsum[right_son(root)])
				return m-rsum[left_son(root)]+1;
			else
				return allocate(op, m+1, r, right_son(root));
	}

	void updata(int op, int ql, int qr, int l, int r, int root)
	{
		if(ql <= l && qr >= r)
		{
			lsum[root] = rsum[root] = msum[root] = op? 0: r-l+1;
			cover[root] = op;
			return;
		}
		int m = (l+r) >> 1;
		push_down(root, m-l+1, r-m);
		if(ql <= m)
			updata(op, ql, qr, l, m, left_son(root));
		if(qr > m)
			updata(op, ql, qr, m+1, r, right_son(root));
		push_up(root, m-l+1, r-m);
	}

	int query(int op, int l, int r, int root)
	{
		if(cover[root] != -1)
			return cover[root];
		if(l == r)
			return 0;
		int m = (l+r) >> 1;
		if(op <= m)
			return query(op, l, m, left_son(root));
		else
			return query(op, m+1, r, right_son(root));
	}
};

SEGMENT_TREE st;

SBT<ELE> sbt;

int s[MAXN], e[MAXN];
int count;

char str[10];

int main()
{
	int n, m, temp;
	int op;
	while(~scanf("%d%d", &n, &m))
	{
		st.build_tree(1, n, 1);
		sbt.init();
		count = 0;
		for(int i = 0; i < m; ++i)
		{
			scanf("%s", str);
			switch(str[0])
			{
			case 'R':	st.updata(0, 1, n, 1, n, 1);
						printf("Reset Now\n");
						sbt.init();
						break;
			case 'N':	scanf("%d", &op);
						if(op > st.msum[1])
						{
							printf("Reject New\n");
						}
						else
						{
							temp = st.allocate(op, 1, n, 1);
							printf("New at %d\n", temp);
							++count;
							s[count] = temp;
							e[count] = temp+op-1;
							st.updata(count, s[count], e[count], 1, n, 1);
							sbt.insert(ELE(s[count], e[count]));
						}
						break;
			case 'F':	scanf("%d", &op);
						temp = st.query(op, 1, n, 1);
						if(temp)
						{
							printf("Free from %d to %d\n", s[temp], e[temp]);
							st.updata(0, s[temp], e[temp], 1, n, 1);
							sbt.erase(ELE(s[temp], e[temp]));
						}
						else
						{
							printf("Reject Free\n");
						}
						break;
			case 'G':	scanf("%d", &op);
						SBT<ELE>::NODE *ret = sbt.select(op);
						if(ret == sbt.NIL)
						{
							printf("Reject Get\n");
						}
						else
						{
							printf("Get at %d\n", ret->key.key1);
						}
						break;
			}
		}
		printf("\n");
	}
	return 0;
}

splay+treap

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>
#include <map>
#include <string>
#include <climits> 
#include <set>
#include <string> 
#include <sstream>
#include <utility>
#include <ctime>

using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::getline;
using std::make_pair;
using std::greater;

const int MAXN(50010);
const int INFI((INT_MAX-1) >> 1);

int n;

struct SPLAY_TREE 
{
	struct NODE
	{
		int cover;
		int key;
		int lsum, rsum, msum;
		int color;
		int size;
		NODE *fa;
		NODE *ch[2];
	};

	NODE pool[MAXN];
	NODE *root, *NIL, *rear;

	void init()
	{
		rear = pool+1;
		NIL = pool;
		NIL->key = -1;
		NIL->cover = -1;
		NIL->size = NIL->lsum = NIL->rsum = NIL->msum = 0;
		NIL->color = MAXN;
		NIL->ch[0] = NIL->ch[1] = NIL->fa = NIL;
		newnode(root, NIL, 0, MAXN);
		newnode(root->ch[1], root, n+1, MAXN);
		build_tree(root->ch[1]->ch[0], root->ch[1], 1, n);
		push_up(root->ch[1]);
		push_up(root);
	}

	void newnode(NODE *&sour, NODE *f, int tk, int tc)
	{
		rear->key = tk;
		rear->color = tc;
		rear->cover = -1;
		rear->size = 1;
		rear->fa = f;
		rear->ch[0] = rear->ch[1] = NIL;
		sour = rear++;
	}

	void push_up(NODE *sour)
	{
		sour->lsum = sour->ch[0]->lsum;
		sour->rsum = sour->ch[1]->rsum;
		sour->msum = 0;
		if(sour->color == 0)
		{
			if(sour->lsum == sour->ch[0]->size)
				sour->lsum += 1+sour->ch[1]->lsum;
			if(sour->rsum == sour->ch[1]->size)
				sour->rsum += 1+sour->ch[0]->rsum;
			sour->msum = sour->ch[0]->rsum+sour->ch[1]->lsum+1;
		}		
		sour->msum = max(sour->msum, max(sour->ch[0]->msum, sour->ch[1]->msum));
		sour->size = sour->ch[0]->size+sour->ch[1]->size+1;
	}

	void push_down(NODE *sour)
	{
		if(sour->cover != -1)
		{
			sour->ch[0]->cover = sour->ch[0]->color = sour->cover;
			sour->ch[1]->cover = sour->ch[1]->color = sour->cover;
			sour->ch[0]->lsum = sour->ch[0]->rsum = sour->ch[0]->msum = sour->cover? 0: sour->ch[0]->size;
			sour->ch[1]->lsum = sour->ch[1]->rsum = sour->ch[1]->msum = sour->cover? 0: sour->ch[1]->size;
			sour->cover = -1;
		}
	}

	void build_tree(NODE *&sour, NODE *f, int l, int r)
	{
		if(l > r)
			return;
		int m = (l+r) >> 1;
		newnode(sour, f, m, 0);
		build_tree(sour->ch[0], sour, l, m-1);
		build_tree(sour->ch[1], sour, m+1, r);
		push_up(sour);
	}

	void rotate(NODE *&sour, int flag)
	{
		NODE *f = sour->fa;
		push_down(f);
		push_down(sour);
		f->ch[!flag] = sour->ch[flag];
		sour->ch[flag]->fa = f;
		sour->fa = f->fa;
		if(f->fa != NIL)
			f->fa->ch[f->fa->ch[1] == f] = sour;
		sour->ch[flag] = f;
		f->fa = sour;
		push_up(f);
	}

	void splay(NODE *sour, NODE *goal)
	{
		push_down(sour);
		while(sour->fa != goal)
		{
			if(sour->fa->fa == goal)
				rotate(sour, sour->fa->ch[0] == sour);
			else
			{
				NODE *f = sour->fa;
				int flag = (f->fa->ch[0] == f);
				if(f->ch[flag] == sour)
					rotate(sour, !flag);
				else
					rotate(f, flag);
				rotate(sour, flag);
			}
		}
		push_up(sour);
		if(goal == NIL)
			root = sour;
	}

	NODE *select(int r, NODE *sour)
	{
		push_down(sour);
		while(sour != NIL && r != sour->ch[0]->size+1)
		{
			if(r <= sour->ch[0]->size)
				sour = sour->ch[0];
			else
			{
				r -= sour->ch[0]->size+1;
				sour = sour->ch[1];
			}
			push_down(sour);
		}
		return sour;
	}

	NODE *find(int op, NODE *sour)
	{
		if(op > sour->msum)
			return NIL;
		push_down(sour);
		NODE *ret;
		while(sour != NIL)
		{
			if(op <= sour->ch[0]->msum)
				sour = sour->ch[0];
			else
				if(sour->color == 0 && op <= sour->ch[0]->rsum+sour->ch[1]->lsum+1)
				{
					ret = select(sour->ch[0]->size-sour->ch[0]->rsum+1, sour);
					break;
				}
				else
					sour = sour->ch[1];
			push_down(sour);
		}
		return ret;
	}

	NODE *allocate(int op)
	{
		NODE *sour;
		sour = select(1, root);
		splay(sour, NIL);
		sour = select(n+2, root);
		splay(sour, root);
		sour = find(op, root->ch[1]->ch[0]);
		return sour;
	}

	void change(int op, int ql, int qr)
	{
		NODE *sour;
		sour = select(ql, root);
		splay(sour, NIL);
		sour = select(qr+2, root);
		splay(sour, root);
		sour = root->ch[1]->ch[0];
		sour->color = sour->cover = op;
		sour->lsum = sour->rsum = sour->msum = op? 0: sour->size;
		push_up(root->ch[1]);
		push_up(root);
	}

	int query(int op)
	{
		NODE *sour = select(op+1, root);
		splay(sour, NIL);
		return root->color;
	}
};

struct TREAP
{
	struct NODE
	{
		int key;
		int fix;
		int size;
		NODE *left, *right;
	};

	NODE pool[MAXN];
	NODE *root, *NIL, *rear;
	int tkey;

	void init()
	{
		rear = pool+1;
		NIL = pool;
		NIL->left = NIL;
		NIL->right = NIL;
		NIL->size = 0;
		NIL->fix = INFI;
		root = NIL;
	}

	void newnode(NODE *&sour, int value)
	{
		rear->key = value;
		rear->fix = rand();
		rear->size = 1;
		rear->left = rear->right = NIL;
		sour = rear++;
	}

	void left_rotate(NODE *&sour)
	{
		NODE *temp = sour->right;
		sour->right = temp->left;
		temp->left = sour;
		temp->size = sour->size;
		sour->size = sour->left->size+sour->right->size+1;
		sour = temp;
	}

	void right_rotate(NODE *&sour)
	{
		NODE *temp = sour->left;
		sour->left = temp->right;
		temp->right = sour;
		temp->size = sour->size;
		sour->size = sour->left->size+sour->right->size+1;
		sour = temp;
	}

	void insert(int value)
	{
		tkey = value;
		insert_(root);
	}

	void insert_(NODE *&sour)
	{
		if(sour == NIL)
		{
			newnode(sour, tkey);
			return;
		}
		++sour->size;
		if(tkey < sour->key)
		{
			insert_(sour->left);
			if(sour->left->fix < sour->fix)
				right_rotate(sour);
		}
		else
		{
			insert_(sour->right);
			if(sour->right->fix < sour->fix)
				left_rotate(sour);
		}
	}

	void erase(int value)
	{
		erase_(root, value);
	}

	void erase_(NODE *&sour, int value)
	{
		if(value == sour->key)
		{
			if(sour->left == NIL || sour->right == NIL)
				sour = sour->left-NIL+sour->right;
			else
			{
				--sour->size;
				if(sour->left->fix < sour->right->fix)
				{
					right_rotate(sour);
					erase_(sour->right, value);
				}
				else
				{
					left_rotate(sour);
					erase_(sour->left, value);
				}
			}
			return;
		}
		--sour->size;
		if(value < sour->key)
			erase_(sour->left, value);
		else
			erase_(sour->right, value);
	}

	NODE *select(int r)
	{
		NODE *sour = root;
		while(sour != NIL && r != sour->left->size+1)
		{
			if(r <= sour->left->size)
				sour = sour->left;
			else
			{
				r -= sour->left->size+1;
				sour = sour->right;
			}
		}
		return sour;
	}
};

SPLAY_TREE splay;
TREAP treap;

int s[MAXN], e[MAXN];
int count;

char str[10];

int main()
{
	int m, op;
	while(~scanf("%d%d", &n, &m))
	{
		splay.init();
		treap.init();
		count = 0;
		SPLAY_TREE::NODE *p1;
		TREAP::NODE *p2;
		int temp;
		for(int i = 0; i < m; ++i)
		{
			scanf("%s", str);
			switch(str[0])
			{
			case 'R':	splay.change(0, 1, n);
						treap.init();
						count = 0;
						printf("Reset Now\n");
						break;
			case 'N':	scanf("%d", &op);
						p1 = splay.allocate(op);
						if(p1 != splay.NIL)
						{
							++count;
							s[count] = p1->key;
							e[count] = p1->key+op-1;
							treap.insert(p1->key);
							splay.change(count, s[count], e[count]);
							printf("New at %d\n", p1->key);
						}
						else
							printf("Reject New\n");
						break;
			case 'F':	scanf("%d", &op);
						temp = splay.query(op);
						if(temp != 0)
						{
							treap.erase(s[temp]);
							splay.change(0, s[temp], e[temp]);
							printf("Free from %d to %d\n", s[temp], e[temp]);
						}
						else
							printf("Reject Free\n");
						break;
			case 'G':	scanf("%d", &op);
						p2 = treap.select(op);
						if(p2 != treap.NIL)
						{
							printf("Get at %d\n", p2->key);
						}
						else
							printf("Reject Get\n");
						break;
			}
		}
		printf("\n");
	}
	return 0;
}