普通平衡树 - Treap

怕被学弟怼 : "你的博客上没有Treap模板啊?"
#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline int cat_max(const int &a,const int &b){return a>b ? a:b;}

inline int cat_min(const int &a,const int &b){return a<b ? a:b;}

const int maxn = 200010;

struct Node{

	Node *ch[2];

	int siz,w,fix;

	void update(){

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

	}

};

struct Treap{

	Node mem[maxn];

	Node *tail,*root,*null;

	Node *bc[maxn];int top;

	Treap(){

		tail = mem;null = tail++;

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

		null->siz = null->w = 0;null->fix = 0x7f7f7f7f;

		root = null;

	}

	Node* newNode(int key){

		Node *p = top ? bc[top--] : tail++;

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

		p->siz = 1;p->w = key;p->fix = rand();

		return p;

	}

	void del(Node* &p){

		bc[++top] = p;

		p = null;

	}

	void turn(Node* &p,int k){

		Node *y = p->ch[k^1];

		p->ch[k^1] = y->ch[k];

		y->ch[k] = p;

		y->siz = p->siz;

		p->update();p = y;

	}

	int val;

	void Insert(Node* &p){

		if(p == null){

			p = newNode(val);

			return;

		}

		p->siz++;

		Insert(p->ch[val >= p->w]);

		if(p->ch[val >= p->w]->fix < p->fix)

			turn(p,val < p->w);

	}

	void Insert(int x){

		val = x;

		Insert(root);

	}

	void Erase(Node* &p){

		if(val == p->w){

			if(p->ch[0] != null && p->ch[1] != null){

				int k = p->ch[0]->fix >= p->ch[1]->fix;

				turn(p,k);

				Erase(p->ch[k]);

			}else{

				Node *y = p->ch[0] == null ? p->ch[1] : p->ch[0];

				del(p);p = y;

			}

		}else Erase(p->ch[val >= p->w]);

		if(p != null) p->update();

	}

	void Erase(int x){

		val = x;

		Erase(root);

	}

	int Kth(int k){

		Node *nw = root;

		while(nw != null){

			if(nw->ch[0]->siz + 1 == k) return nw->w;

			if(nw->ch[0]->siz + 1 >  k) nw = nw->ch[0];

			else k -= nw->ch[0]->siz + 1,nw = nw->ch[1];

		}

	}

	int rank(int x){

		int ret = 1;

		Node *nw = root;

		while(nw != null){

			if(x <= nw->w) nw = nw->ch[0];

			else{

				ret += nw->ch[0]->siz + 1;

				nw = nw->ch[1];

			}

		}return ret;

	}

}*zs = new Treap();

int main(){

	srand(666);

	int n;read(n);

	int opt,x;

	while(n--){

		read(opt);read(x);

		switch(opt){

			case 1:

				zs->Insert(x);

				break;

			case 2:

				zs->Erase(x);

				break;

			case 3:

				printf("%d\n",zs->rank(x));

				break;

			case 4:

				printf("%d\n",zs->Kth(x));

				break;

			case 5:

				printf("%d\n",zs->Kth(zs->rank(x)-1));

				break;

			case 6:

				printf("%d\n",zs->Kth(zs->rank(x+1)));

				break;

		}

	}

	getchar();getchar();

	return 0;

}
巴特西

普通平衡树 - Treap

最新文章

热门文章
