Code:Treap/C++

//不旋转的treap
struct Node
{
	public:
		int x,y,ran,sum;
		int a;
		Node(){a=0;x=0;y=0;ran=rand();sum=1;}
};
 
struct Treap
{
	public:
		int root,n;
		Node d[N];
		int merge(int x,int y);
		pair<int,int> split(int x,int y);
}Tr;
 
int Treap::merge(int x,int y)
{
	if(!x || !y)return x+y;
	if(d[x].ran>d[y].ran)
	{
		d[x].y=merge(d[x].y,y);
		d[x].sum=d[d[x].x].sum+d[d[x].y].sum+1;
		return x;
	}
	d[y].x=merge(x,d[y].x);
	d[y].sum=d[d[y].x].sum+d[d[y].y].sum+1;
	return y;
}
 
pair<int,int> Treap::split(int x,int y)
{
	if(!x)return mp(0,0);
	if(d[d[x].x].sum>=y)
	{
		pair<int,int> p=split(d[x].x,y);
		d[x].x=p.y;
		d[x].sum=d[d[x].x].sum+d[d[x].y].sum+1;
		return mp(p.x,x);
	}
	pair<int,int> p=split(d[x].y,y-d[d[x].x].sum-1);
	d[x].y=p.x;
	d[x].sum=d[d[x].x].sum+d[d[x].y].sum+1;
	return mp(x,p.y);
}

//Written By CmYkRgB123
#include <iostream>
#include <ctime>
#define MAX 100
 
using namespace std;
 
typedef struct
{
	int l,r,key,fix;
}node;
 
class treap
{
public:
	node p[MAX];
	int size,root;
	treap()
	{
		srand(time(0));
		size=-1;
		root=-1;
	}
 
	void rot_l(int &x)
	{
		int y=p[x].r;
		p[x].r=p[y].l;
		p[y].l=x;
		x=y;
	}
 
	void rot_r(int &x)
	{
		int y=p[x].l;
		p[x].l=p[y].r;
		p[y].r=x;
		x=y;
	}
 
	void insert(int &k,int tkey)
	{
		if (k==-1)
		{
			k=++size;
			p[k].l=p[k].r=-1;
			p[k].key=tkey;
			p[k].fix=rand();
		}
		else
		if (tkey<p[k].key)
		{
			insert(p[k].l,tkey);
			if (p[ p[k].l ].fix>p[k].fix)
				rot_r(k);
		}
		else
		{
			insert(p[k].r,tkey);
			if (p[ p[k].r ].fix>p[k].fix)
				rot_l(k);
		}
 
	}
 
	void remove(int &k,int tkey)
	{
		if (k==-1) return;
		if (tkey<p[k].key)
			remove(p[k].l,tkey);
		else if (tkey>p[k].key)
			remove(p[k].r,tkey);
		else
		{
			if (p[k].l==-1 && p[k].r==-1)
				k=-1;
			else if (p[k].l==-1)
				k=p[k].r;
			else if (p[k].r==-1)
				k=p[k].l;
			else
			if (p[ p[k].l ].fix < p[ p[k].r ].fix)
			{
				rot_l(k);
				remove(p[k].l,tkey);
			}
			else
			{
				rot_r(k);
				remove(p[k].r,tkey);
			}
		}
	}
 
	void print(int k)
	{
		if (p[k].l!=-1)
			print(p[k].l);
		cout << p[k].key << " : " << p[k].fix << endl;
		if (p[k].r!=-1)
			print(p[k].r);
	}
};
 
treap T;
 
int main()
{
 
	int i;
	for (i=3;i>=1;i--)
		T.insert(T.root,i);
	T.print(T.root);
	for (i=3;i>=1;i--)
	{
		cout << endl;
		T.remove(T.root,i);
		T.print(T.root);
	}
	return 0;
}

//使用指针的treap  by zjf
#include <time.h>
#include <stdlib.h>
#include <iostream>
 
using namespace std;
 
typedef struct treapnode;
typedef struct treapnode *treap;
 
struct treapnode
{
    int key,fix;
    treap left,right;
};
 
treap nullnode,root;
 
void initialize()
{
    nullnode = new treapnode;
    nullnode->left = nullnode->right = nullnode;
    root=nullnode;
}
 
void sigrotl(treap& k1)
{
    treap k2;
    k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1 = k2;
}
 
void sigrotr(treap& k1)
{
    treap k2;
    k2 = k1->left;
    k1->left = k2->right;
    k2->right = k1;
    k1 = k2;
}
 
void insert(treap& t,int x)
{
    if(t == nullnode)
    {
        t = new treapnode;
        t->left = t->right = nullnode;
        t->key = x;
        t->fix = rand();
    }
    else
    if(t->key == x)return;
    else
    if(x < t->key)
    {
        insert(t->left,x);
        if(t->left->fix > t->fix)sigrotr(t);
    }
    else
    {
        insert(t->right,x);
        if(t->right->fix > t->fix)sigrotl(t);
    }
}    
 
void remove(treap& t,int x)
{
    if(t == nullnode)return;
    if(x > t->key)remove(t->right,x);
    else if(x < t->key)remove(t->left,x);
    else
    {
        if(t->left == nullnode && t->right == nullnode)
        {
            delete t;
            t=nullnode;
        }
        else if(t->left == nullnode)
        {
            treap tmp = t;
            t = t->right;
            delete tmp;
        }
        else if(t->right == nullnode)
        {
            treap tmp = t;
            t = t->left;
            delete tmp;
        }
        else
        if(t->left->fix < t->right->fix)
        {
            sigrotl(t);
            remove(t->left,x);
        }
        else
        {
            sigrotr(t);
            remove(t->right,x);
        }
    }
}    
 
void list(treap t)
{
    if(t == nullnode)return;cout << t->key << endl;
    list(t->left);
 
    list(t->right);
}
 
int main()
{
    initialize();
    insert(root,1);
    insert(root,2);
    insert(root,3);
    insert(root,4);
    insert(root,5);
    list(root);
    system("pause");
}

发一个我的。 主要是运用了孩子数组c来简化代码。 并且把null节点的优先级设为inf，方便删除 By WJMZBMR..题目是SPOJ的ORDERSET。。

#include<cstdio>
#include<cstdlib>
using namespace std;
const int inf=~0U>>1;
class treap
{
	struct node
	{
		int value,key,size;
		node(int v,node*n):value(v)
		{c[0]=c[1]=n;size=1;key=rand()-1;}
		void rz(){size=c[0]->size+c[1]->size+1;}
		node*c[2];
	}*root,*null;
	void rot(node*&t,bool d)
	{
		node*c=t->c[d];
		t->c[d]=c->c[!d];
		c->c[!d]=t;
		t->rz();c->rz();
		t=c;
	}
	void insert(node*&t,int x)
	{
			if(t==null)	{t=new node(x,null);return;}
			if(x==t->value) return;
			bool d=x>t->value;
			insert(t->c[d],x);
			if(t->c[d]->key<t->key)
				rot(t,d);
			else
				t->rz();
	}
	void Delete(node*&t,int x)
	{
		   if(t==null) return;
		   if(t->value==x)
			{
				bool d=t->c[1]->key<t->c[0]->key;
				if(t->c[d]==null)
				{
					delete t;
					t=null;
					return;
				}
				rot(t,d);
				Delete(t->c[!d],x);
			}
			else
			{
				bool d=x>t->value;
				Delete(t->c[d],x);
			}
			t->rz();
	}
	int select(node*t,int k)
	{
		int r=t->c[0]->size;
		if(k==r) return t->value;
		if(k<r) return select(t->c[0],k);
		return select(t->c[1],k-r-1);
	}
	int rank(node*t,int x)
	{
		if(t==null) return 0;
		int r=t->c[0]->size;
		if(x==t->value) return r;		
		if(x<t->value) return rank(t->c[0],x);
		return r+1+rank(t->c[1],x);
	}
	public:
	treap()
	{
		null=new node(0,0);null->size=0;null->key=inf;
		root=null;
	}
	void ins(int x)
	{
		insert(root,x);
	}
	int sel(int k)
	{
		if(k>root->size) return -inf;
		return select(root,k-1);
	}
	int ran(int x)
	{
		return rank(root,x);
	}
	void del(int x)
	{
		Delete(root,x);
	}	
}T;
int main()
{
	//freopen("in","r",stdin);
	int m;scanf("%d\n",&m);	
	char t;int x,tmp;
	while(m--)
	{
		scanf("%c %d\n",&t,&x);
		switch(t)
		{
			case 'I':T.ins(x);break;
			case 'D':T.del(x);break;
			case 'K':tmp=T.sel(x);if(tmp==-inf)printf("invalid\n");else printf("%d\n",tmp);break;
			case 'C':printf("%d\n",T.ran(x));break;
		}		
	}
}

/*
  Author: lqhl
  Problem: HNOI 2004 day1 pet 宠物收养所
*/
#include <cstdlib>
#include <fstream>
#include <iostream>
using namespace std;
 
const int INF = 1<<30;
const int DIVISOR = 1000000;
 
template <class DType>
class Treap {
	private:
	typedef struct node;
	typedef struct node *pnode;
	struct node {
		DType key;
		int count, total;
		pnode left, right;
		int priority;
	};
 
	pnode null, root;
 
	void left_rotate(pnode &cur) {
		pnode tmp;
		tmp = cur->left;
		cur->left = tmp->right;
		tmp->right = cur;
		tmp->total = cur->total;
		cur->total = cur->left->total + cur->right->total + cur->count;
		cur = tmp;
	}
 
	void right_rotate(pnode &cur) {
		pnode tmp;
		tmp = cur->right;
		cur->right = tmp->left;
		tmp->left = cur;
		tmp->total = cur->total;
		cur->total = cur->left->total + cur->right->total + cur->count;
		cur = tmp;
	}
 
	void insert_node(pnode &cur, DType key) {
		if (cur == null) {
			cur = new struct node;
			cur->key = key;
			cur->count = 1;
			cur->total = 1;
			cur->left = null;
			cur->right = null;
			cur->priority = rand();
		}
		else if (key < cur->key) {
			insert_node(cur->left, key);
			if (cur->left->priority < cur->priority)
				left_rotate(cur);
		}
		else if (key > cur->key) {
			insert_node(cur->right, key);
			if (cur->right->priority < cur->priority)
				right_rotate(cur);
		}
		else
			cur->count++;
		cur->total = cur->left->total + cur->right->total + cur->count;
	}
 
	void delete_node (pnode &cur, DType key) {
		if (cur != null)
			if (key < cur->key)
				delete_node(cur->left, key);
			else if (key > cur->key)
				delete_node(cur->right, key);
			else if (cur->count > 1)
				cur->count--;
			else if ((cur->left == null) && (cur->right == null)) {
				delete cur;
				cur = null;
			}
			else {
				if (cur->left->priority < cur->right->priority)
					left_rotate(cur);
				else
					right_rotate(cur);
				delete_node(cur, key);
			}
		cur->total = cur->left->total + cur->right->total + cur->count;
	}
 
	void erase(pnode cur) {
		if (cur->left != null)
			erase(cur->left);
		if (cur->right != null)
			erase(cur->right);
		delete cur;
	}
 
	public:
	Treap () {
		null = new struct node;
		null->key = INF;
		null->count = 0;
		null->total = 0;
		null->left = null;
		null->right = null;
		null->priority = INF;
		root = null;
	}
 
	~Treap () {
		erase(root);
		delete null;
		delete root;
	}
 
	void insert(DType key) {
		insert_node(root, key);
	}
 
	void del(DType key) {
		delete_node(root, key);
	}
 
	DType find_nearest(DType key) {
		DType left, right;
		pnode cur;
		cur = root;
		left = -INF;
		right = INF;
		while (cur != null) {
			if (key < cur->key) {
				if (cur->key < right)
					right = cur->key;
				cur = cur->left;
			}
			else {
				if (cur->key > left)
					left = cur->key;
				cur = cur->right;
			}
		}
		if (key - left <= right - key)
			return left;
		else
			return right;
	}
};
 
Treap <int> bst;
 
int main() {
	FILE *fin = fopen("pet.in", "r");
	FILE *fout = fopen("pet.out", "w");
	int n,
		kind = 0, ty, num,
		ans = 0, tmp;
	fscanf(fin, "%d\n", &n);
	for (int i = 0; i < n; i++) {
		fscanf(fin, "%d %d\n", &ty, &num);
		if (ty) {
			if (kind >= 0)
				bst.insert(num);
			else {
				tmp = bst.find_nearest(num);
				ans += abs(num - tmp);
				ans %= DIVISOR;
				bst.del(tmp);
			}
			kind++;
		}
		else {
			if (kind <= 0)
				bst.insert(num);
			else {
				tmp = bst.find_nearest(num);
				ans += abs(num - tmp);
				ans %= DIVISOR;
				bst.del(tmp);
			}
			kind--;
		}
	}
	fprintf(fout, "%d\n", ans);
}

#include<iostream>
#include<fstream>
using namespace std;
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
 
typedef struct Node {
	int key,pri;
	struct Node *lc, *rc;
} node, *treap;
 
int n;
treap root=NULL , h;
 
void zig(treap &t) {
	h = t->lc ;
	t->lc = h->rc ;
	h->rc = t ;
	t = h ;
}
 
void zag(treap &t) {
	h = t->rc ;
	t->rc = h->lc ;
	h->lc = t ;
	t = h ;
}
 
void ins(treap &t,const int x) {
	if(t==NULL) {
		t=new node;
		t->key=x;
		t->pri=rand();
		t->lc = t->rc = NULL ;
	}
	else
		if( x < t->key ) {
			ins( t->lc , x );
			if( t->lc->pri < t->pri )
				zig(t);
		}
		else {
			ins( t->rc , x );
			if( t->rc->pri < t->pri )
				zag(t);
		}
}
 
void del(treap &t,const int x) {
	if(t==NULL) return;
	if( t->key == x )
		if( t->lc == NULL && t->rc == NULL ) {
			delete t;
			t=NULL;
		}
		else if( t->lc == NULL ) {
				h=t;
				t=t->rc;
				delete h;
			 }
			 else if( t->rc == NULL ) {
					h=t;
					t=t->lc;
					delete h;
				  }
				  else
					if( t->lc->pri < t->rc->pri ) {
						zig(t);
						del(t->rc,x);
					}
					else {
						zag(t);
						del(t->lc,x);
					}
	else if( x < t->key )
			del(t->lc,x);
		else
			del(t->rc,x);
}
 
void order(treap t) {
	if(t==NULL) return;
	order(t->lc);
	printf(" %d",t->key);
	order(t->rc);
}
 
bool find(treap t,const int x) {
	if( t == NULL )
		return false;
	else;
	if( t->key == x )
		return true;
	else
		if( x < t->key )
			return find( t->lc, x );
		else
			return find( t->rc, x );
}
 
void dispose(treap &t) {
	if(t==NULL)
		return;
	dispose(t->lc);
	dispose(t->rc);
	delete t;
	t=NULL;
}
 
int main() {
	scanf("%d",&n);
	srand(121);
	char c;
	int a;
	for(int i=1;i<=n;++i) {
		while( ! isalpha( c = fgetc(stdin) ) ) ;
		scanf("%d",&a);
		if(c=='I')		//Insert
			ins(root,a);
		if(c=='D')		//Delete
			del(root,a);
		if(c=='O') {	//Order
			order(root);
			puts("");
		}
		if(c=='F')		//Find
			if( find(root,a) )
				printf("%d has been found.\n",a);
			else
				printf("%d is not here\n",a);
	}
	dispose(root);		//Dispose
	return 0;
}

/* 
LANG: C++ 
Author By : MiYu 
Program   : PKU 3481  double queue
*/ 
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
#define MEM(x,y) memset(x,y,sizeof(x)) 
const int MaxN = 100010;
int cnt = 1, rt = 0;
struct Treap {
       int key, val, pri, ch[2];
       void set ( int x, int y, int z ) { 
            key = x, val = y, pri = z, ch[0]=ch[1]=0; }  
}T[MaxN];
void rotate ( int &x, int f ) {  // f: 1. 右旋,  0. 左旋 
     int y = T[x].ch[!f];
     T[x].ch[!f] = T[y].ch[f];
     T[y].ch[f] = x;
     x = y;     
}
void insert ( int &x, int key, int val ) {  // 插入元素 
     if ( x == 0 ) { 
         T[x = cnt ++].set ( key, val, rand () );     
     } else {
         int f = key < T[x].key; 
         insert ( T[x].ch[!f], key, val );
         if ( T[x].pri < T[ T[x].ch[!f] ].pri ) rotate ( x, f );    
     }    
}
void del ( int &x, int key ) {  //删除指定元素值 
     if ( T[x].key == key ) {
         if ( !T[x].ch[0] || !T[x].ch[1] ) {
             if ( !T[x].ch[0] ) x = T[x].ch[1];
             else x = T[x].ch[0];     
         } else {
             int f = T[ T[x].ch[0] ].pri > T[ T[x].ch[1] ].pri;
             rotate ( x, f );        
             del ( T[x].ch[f], key );
         }    
     } else {
         int f = T[x].key > key;
         del ( T[x].ch[!f], key );       
     }     
}
int get ( int x, int f ) {
    while ( T[x].ch[f] ) x = T[x].ch[f];
    return x;    
}
inline bool read(int &num) {
        char in;bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;} else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9') num*=10,num+=in-'0'; 
        if(IsN) num=-num;
        return true;
}
int main ()
{ 
    srand ( time ( NULL ) );
    int N, key, val;
    while ( read ( N ), N ) { 
          if ( N == 1 ) {
              read ( val ), read ( key );
              insert ( rt, key, val );    
          } else if ( N == 2 ) {
              int x = get ( rt, 1 );
              if ( x ) printf ( "%d\n", T[x].val ),del ( rt, T[x].key );      
              else puts ( "0" ); 
          } else if ( N == 3 ) {
              int x = get ( rt, 0 );
              if ( x ) printf ( "%d\n", T[x].val ),del ( rt, T[x].key ); 
              else puts ( "0" );    
          }      
    } 
    return 0;
}

/* 
LANG: C++ 
Author By : YangZX
一个以Treap实现的BST模板，支持的操作比较齐全：
1.void insert(T x) 将x插入平衡树
2.void erase(T) 将一个x从平衡树中移除
3.T select(int kth) 返回第k小的元素
4.void sort(T* arr) 按照从小到大顺序将所有元素输出到arr
5.int count(T) 返回T在树中的个数
*/ 
#include <iostream>
using namespace std;
template<typename T>
class BST
{
	public:
		void insert(const T& x);
		void erase(const T& x);
		int count(const T& x);
		const T& select(int kth);
		void sort(T* arr);
		int size();
		BST(int n);
		~BST();
	private:
		typedef int Treap;
		int newnode();
		void SRL(Treap&);
		void SRR(Treap&);
		void foreach(Treap &rt, T* arr);
		const T& slt(int kth, Treap &rt);
		int bstcnt(const T& x, Treap &rt);
		void ers(const T&, Treap& rt);
		void ins(const T&, Treap& rt);
		Treap rt;
		struct node{
			Treap L, R;
			T v;
			int num, size, prio;
		}*Tree;
		int cnt, sortcnt;
		static const int MAXPRIO = 1 <<28;
};
template<typename T>
BST<T>::BST(int x)
{
	srand(time(NULL));
	Tree = new node[x];
	cnt = rt = 0;
	Tree[0].prio = MAXPRIO;
}
template<typename T>
BST<T>::~BST()
{
	delete[] Tree;
}
template<typename T>
int BST<T>::size()
{
	if(!rt)
		return 0;
	return Tree[rt].size;
}
template<typename T>
int BST<T>::count(const T& x)
{
	bstcnt(x, rt);
}
template<typename T>
void BST<T>::foreach(Treap &rt, T* arr)
{
	if(!rt)
		return;
	foreach(Tree[rt].L, arr);
	for(int i=1; i<=Tree[rt].num; i++)
		arr[sortcnt++] = Tree[rt].v;
	foreach(Tree[rt].R, arr);
}
template<typename T>
int BST<T>::bstcnt(const T& x, Treap &rt)
{
	if(!rt)
		return 0;
	if(Tree[rt].v == x)
		return Tree[rt].num;
	if(x < Tree[rt].v)
		return bstcnt(x, Tree[rt].L);
	else
		return bstcnt(x, Tree[rt].R);
}
template<typename T>
void BST<T>::sort(T* a)
{
	sortcnt = 0;
	foreach(rt, a);
}
template<typename T>
int BST<T>::newnode()
{
	Tree[++cnt].prio = rand();
	Tree[cnt].L = Tree[cnt].R = 0;
	return cnt;
}
template<typename T>
const T& BST<T>::select(int k)
{
	return slt(k, rt);
}
template<typename T>
const T& BST<T>::slt(int k, Treap &rt)
{
	if(k >= Tree[Tree[rt].L].size + 1 && k <= Tree[Tree[rt].L].size + Tree[rt].num)
		return Tree[rt].v;
	else if(k <= Tree[Tree[rt].L].size)
		return slt(k, Tree[rt].L);
	else
		return slt(k - Tree[Tree[rt].L].size - Tree[rt].num, Tree[rt].R);
}
template<typename T>
void BST<T>::insert(const T& x)
{
	ins(x, rt);
}
template<typename T>
void BST<T>::ins(const T& x, Treap& rt)
{
	if(!rt){
		rt = newnode();
		Tree[rt].v = x;
		Tree[rt].num = Tree[rt].size = 1;
		return;
	}
	if(Tree[rt].v == x){
		Tree[rt].num++;
		Tree[rt].size++;
		return;
	}else if(x < Tree[rt].v){
		ins(x, Tree[rt].L);
		if(Tree[Tree[rt].L].prio < Tree[rt].prio)
			SRL(rt);
	}else{
		ins(x, Tree[rt].R);
		if(Tree[Tree[rt].R].prio < Tree[rt].prio)
			SRR(rt);
	}
	Tree[rt].size = Tree[Tree[rt].L].size + Tree[Tree[rt].R].size + Tree[rt].num;
}
template<typename T>
void BST<T>::erase(const T& x)
{
	ers(x, rt);	
}
template<typename T>
void BST<T>::ers(const T& x, Treap &rt)
{
	if(!rt)
		return;
	if(Tree[rt].v == x && Tree[rt].num > 0){
		Tree[rt].num--;
		Tree[rt].size--;
		return;
	}else if(Tree[rt].v == x)
		return;
	if(x < Tree[rt].v)
		ers(x, Tree[rt].L);
	else
		ers(x, Tree[rt].R);
	Tree[rt].size = Tree[Tree[rt].L].size + Tree[Tree[rt].R].size + Tree[rt].num;
}
template<typename T>
void BST<T>::SRL(Treap &rt)
{
	Treap L;
	L = Tree[rt].L;
	Tree[rt].L = Tree[L].R;
	Tree[L].R = rt;
	Tree[rt].size = Tree[Tree[rt].L].size + Tree[Tree[rt].R].size + Tree[rt].num;
	Tree[L].size = Tree[rt].size + Tree[Tree[L].L].size + Tree[L].num;
	rt = L;
}
template<typename T>
void BST<T>::SRR(Treap &rt)
{
	Treap R;
	R = Tree[rt].R;
	Tree[rt].R = Tree[R].L;
	Tree[R].L = rt;
	Tree[rt].size = Tree[Tree[rt].L].size + Tree[Tree[rt].R].size + Tree[rt].num;
	Tree[R].size = Tree[rt].size + Tree[Tree[R].R].size + Tree[R].num;
	rt = R;
}
 
/*Demo*/
int main()
{
 
	cin>>n>>k;
	int i, x;
	BST<int> st(n);
	for(i=1; i<=n; i++){
		cin>>x;
		st.insert(x);
	}
	cout<<st.select(k)<<endl;
 
	return 0;
}

/*
 * Treap指针-小根堆实现样例程序 for 数算实习
 * AUTH: Nettle
 * DATE: 2012.11.7
 */
 
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
using namespace std;
 
class cTreap {
	/*
	 * 指针实现Treap
	 * weight采用小根堆的方式维护
	 */
private:
	struct sNode {																		// Treap节点
		int data;																		// data域
		int weight;																		// weight域
		sNode *lch, *rch;																// 左右儿子的指针
		sNode(int key):data(key), weight(rand()) {										// 构造函数初始化
			lch = rch = NULL;
		}
	};
	typedef sNode* pNode;																// 定义指针类型
 
	pNode root;																			// 根指针
 
	void leftRotate(pNode &rt) {														// 左旋
		pNode p = rt -> lch;
		rt -> lch = p -> rch;
		p -> rch = rt;
		rt = p;
		return ;
	}
 
	void rightRotate(pNode &rt) {														// 右旋
		pNode p = rt -> rch;
		rt -> rch = p -> lch;
		p -> lch = rt;
		rt = p;
		return ;
	}
 
	void removeAll(pNode &rt) {															// 删除所有节点
		if (!rt) return ;
		removeAll(rt -> lch);
		removeAll(rt -> rch);
		delete rt;
		rt = NULL;
		return ;
	}
 
	void insert(const int key, pNode &rt) {												// 递归插入节点
		if (!rt) {																		// 如果当前节点为空的叶子节点
			rt = new sNode(key);
			return ;
		}
		if (key < rt -> data) {															// 插入值小于当前值，插入左子树
			insert(key, rt -> lch);
			if (rt -> lch -> weight < rt -> weight)										// 维护weight域
				leftRotate( rt );
		}	else {																		// 插入值大于等于当前值，插入右子树
			insert(key, rt -> rch);
			if (rt -> rch -> weight < rt -> weight)										// 维护weight域
				rightRotate( rt );
		}
		return ;
	}
 
	void remove(const int key, pNode &rt) {
		if (!rt) return ;																// 如果访问到空节点，删除值不存在
		if (rt -> data == key) {														// 当前值为删除值
			if (!rt -> lch && !rt -> rch) {												// 没有儿子，直接删除
				delete rt;
				rt = NULL;
				return ;
			}	
			if (!rt -> rch) {															// 只有左儿子，将左儿子旋转到当前位置
				leftRotate( rt );
				remove(key, rt -> rch);													// 继续递归删除
				return ;
			}
			if (!rt -> lch) {															// 只有右儿子，将右儿子旋转到当前位置
				rightRotate( rt );
				remove(key, rt -> lch);                                                 // 继续递归删除
				return ;
			}
			if (rt -> lch -> weight < rt -> rch -> weight) {							// 两个儿子都存在，选择权值小的一个
				leftRotate( rt );
				remove(key, rt -> rch);
			}	else {
				rightRotate( rt );
				remove(key, rt -> lch);
			}
			return ;
		}
		if (key < rt -> data) remove(key, rt -> lch);									// 若当前值不等于删除值，根据删除值查找子树
			else remove(key, rt -> rch);
		return ;
	}
 
	bool quary(const int key, pNode rt) {												// 查询key值是否在Treap中
		if (!rt) return false;															// 查找到空叶子节点，key不存在于Treap
		if (rt -> data == key) return true;												// 查找到目标值
		if (rt -> data < key) return quary(key, rt -> lch);								// 根据当前值继续二分查找
			else return quary(key, rt -> rch);
	}
 
	void print(pNode rt) {																// 使用括号表示法递归打印当前树
		if (!rt) return ;
		cout << "[";
		print(rt -> lch);
		cout << rt -> data << ':' << rt -> weight;
		print(rt -> rch);
		cout << "]";
		return ;
	}
 
public:
	cTreap():root(NULL) {																// 构造函数，初始化随机器
		srand(time(NULL));
	}
	~cTreap() {																			// 析构函数
		removeAll( root );
	}
 
	void insert(const int key) {														// 插入key值
		insert(key, root);
		return ;
	}
 
	void remove(const int key) {														// 删除key值
		remove(key, root);
		return ;
	}
 
	bool quary(const int key) {															// 查询key值
		return quary(key, root);
	}
 
	void print() {																		// 打印Treap
		if (root) print(root);
		else cout << "Empty treap";
		cout << endl;
		return ;
	}
};
 
int main() {
	/*
	 * Treap样例程序
	 * 5种指令：
	 * +-----+-----------------------------------+
	 * | 格式| 含义                              |
	 * +-----+-----------------------------------+
	 * | I x | 向Treap中插入x                    |
	 * | D x | 删除Treap中的x(有多个x只删除一个) |
	 * | Q x | 查询x是否在Treap中                |
	 * | P	 | 括号表示法打印Treap               |
	 * | E	 | 退出程序                          |
	 * +-----+-----------------------------------+
	 */
	cTreap *myTreap = new cTreap;
	string cmd;																			// 指令
	int key;																			// key值
	do {
		cin >> cmd;
		switch (cmd[0]) {
		case 'I':
			cin >> key;
			myTreap -> insert(key);
			break;
		case 'D':
			cin >> key;
			myTreap -> remove(key);
			break;
		case 'Q':
			cin >> key;
			if (myTreap -> quary(key)) cout << 'T' << endl;
			else cout << 'F' << endl;
			break;
		case 'P':
			myTreap -> print();
			break;
		case 'E':
			return 0;
		}
	}	while (true);
	delete myTreap;
    return 0;
}