BZOJ 3224: Tyvj 1728 普通平衡树 （Scapegoat tree）

BZOJ3224 水题一样。 为了练习一下替罪羊树，用这个来搞了一发。 替罪羊树可以不需要旋转来保存平衡。 当然在这题还看不到他的优势。

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1956 Solved: 769 [Submit][Status]

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数)

Input

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数，表示对应答案

Sample Input

10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598

Sample Output

106465 84185 492737

HINT

1.n的数据范围：n<=100000

2.每个数的数据范围：[-1e7,1e7]

Source

平衡树

题意很简单。 直接替罪羊树练习了一发。

/* ***************

Author        :kuangbin

Created Time  :2014/9/30 8:13:45

File Name     :E:\2014ACM\专题学习\数据结构\ScapeGoatTree\BZOJ3224.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 200010;

const double alpha = 0.75;

struct Node{

	Node *ch[2];

	int size,key,nodeCount;

	bool exist;

	bool isBad(){

		return ch[0]->nodeCount > alpha*nodeCount + 5 || ch[1]->nodeCount > alpha*nodeCount + 5;

	}

	void push_up(){

		size = exist + ch[0]->size + ch[1]->size;

		nodeCount = 1 + ch[0]->nodeCount + ch[1]->nodeCount;

	}

};

struct ScapeGoatTree{

	Node pool[MAXN];

	Node *tail,*root,*null;

	Node *bc[MAXN];//内存回收

	int bc_top;

	void init(){

		tail = pool;

		null = tail++;

		null->ch[0] = null->ch[1] = null;

		null->size = null->key = null->nodeCount = 0;

		root = null;

		bc_top = 0;

	}

	inline Node *newNode(int key){

		Node *p;

		if(bc_top)p = bc[--bc_top];

		else p = tail++;

		p->ch[0] = p->ch[1] = null;

		p->size = 1;

		p->key = key;

		p->nodeCount = 1;

		p->exist = true;

		return p;

	}

	inline void Travel(Node *p,vector<Node \*>&v){

		if(p == null)return;

		Travel(p->ch[0],v);

		if(p->exist)v.push_back(p);

		else bc[bc_top++] = p;

		Travel(p->ch[1],v);

	}

	inline Node *divide(vector<Node \*>&v,int l,int r){

		if(l >= r)return null;

		int mid = (l+r)/2;

		Node *p = v[mid];

		p->ch[0] = divide(v,l,mid);

		p->ch[1] = divide(v,mid+1,r);

		p->push_up();

		return p;

	}

	inline void rebuild(Node *&p){

		vector<Node *>v;

		Travel(p,v);

		p = divide(v,0,v.size());

	}

	Node **insert(Node *&p,int val){

		if(p == null){

			p = newNode(val);

			return &null;

		}

		else {

			p->size++;

			p->nodeCount++;

			int d = (val >= p->key);

			Node **res = insert(p->ch[d],val);

			if(p->isBad())res = &p;

			return res;

		}

	}

	//插入一个值为val的点

	void insert(int val){

		Node **p = insert(root,val);

		if(*p != null)rebuild(*p);

	}

	//删除第id个点

	void erase(Node *p,int id){

		if(p->exist && id == p->ch[0]->size+1){

			p->exist = 0;

			p->size--;

			return;

		}

		p->size--;

		if(id <= p->ch[0]->size+p->exist)

			erase(p->ch[0],id);

		else erase(p->ch[1],id - p->ch[0]->size - p->exist);

	}

	//查询小于val的数的个数+1

	int rank(int val){

		Node *now = root;

		int ans = 1;

		while(now != null){

			if(now->key >= val)now = now->ch[0];

			else {

				ans += now->ch[0]->size + now->exist;

				now = now->ch[1];

			}

		}

		return ans;

	}

	int get_kth(int k){

		Node *now = root;

		while(now != null){

			if(now->exist && k == now->ch[0]->size+1)

				return now->key;

			else if(now->ch[0]->size >= k)now = now->ch[0];

			else {

				k -= now->ch[0]->size + now->exist;

				now = now->ch[1];

			}

		}

	}

	//删除一个值为val的点

	void erase(int val){

		erase(root,rank(val));

		if(root->size < alpha*root->nodeCount)

			rebuild(root);

	}

}tree;

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n;

	while(scanf("%d",&n) == 1){

		tree.init();

		int op,x;

		while(n--){

			scanf("%d%d",&op,&x);

			if(op == 1)tree.insert(x);

			else if(op == 2) tree.erase(x);

			else if(op == 3)printf("%d\n",tree.rank(x));

			else if(op == 4)printf("%d\n",tree.get_kth(x));

			else if(op == 5)printf("%d\n",tree.get_kth(tree.rank(x)-1));

			else printf("%d\n",tree.get_kth(tree.rank(x+1)));

    	}
    }
    return 0;

}