题目链接：洛谷 P3369 【模板】普通平衡树.
这只是一篇用来存代码的博客。平衡树使用无旋Treap实现。
将保存不同语言（偏竞赛风格）的代码作为对比。

10多年的台州网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。全网整合营销推广的优势是能够根据用户设备显示端的尺寸不同，自动调整台州建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。成都创新互联公司从事“台州网站设计”,“台州网站推广”以来，每个客户项目都认真落实执行。文章目录

• • • C++ 11
    • Python 3.6
    • Java 8

C++ 11

#include#include#include#includestruct node{int val,rk,siz;
	node *ls,*rs;
	node(int val=0):val(val){rk=rand();siz=1;ls=rs=NULL;}
	void upd(){siz=1;
		if(ls!=NULL)
			siz+=ls->siz;
		if(rs!=NULL)
			siz+=rs->siz;
	}
}*rt;

void split(node *o,node *&a,node *&b,const int &v){if(o==NULL){a=b=NULL;
		return;
	}
	if(o->val<=v){a=o;
		split(o->rs,a->rs,b,v);
	}
	else{b=o;
		split(o->ls,a,b->ls,v);
	}
	o->upd();
}
void merge(node *&o,node *a,node *b){if(a==NULL){o=b;
		return;
	}
	if(b==NULL){o=a;
		return;
	}
	if(a->rkrk){o=a;
		merge(o->rs,a->rs,b);
	}
	else{o=b;
		merge(o->ls,a,b->ls);
	}
	o->upd();
}
void insert(node *&o,int v){node *l,*r,*u=new node(v);
	split(o,l,r,v);
	merge(l,l,u);
	merge(o,l,r);
}
void erase(node *&o,int v){node *l,*r,*u;
	split(o,l,r,v);
	split(l,l,u,v-1);
	if(u!=NULL){node *t=u;
		merge(u,u->ls,u->rs);
		delete t;
	}
	merge(l,l,u);
	merge(o,l,r);
}
int find_by_order(const node *o,int k){if(o==NULL)
		return -1;
	int lsiz=0;
	if(o->ls!=NULL)
		lsiz=o->ls->siz;
	if(k==lsiz+1)
		return o->val;
	if(k<=lsiz)
		return find_by_order(o->ls,k);
	else
		return find_by_order(o->rs,k-lsiz-1);
}
int order_of_key(node *&o,int v){node *l,*r;
	split(o,l,r,v-1);
	int res;
	if(l==NULL)
		res=1;
	else
		res=l->siz+1;
	merge(o,l,r);
	return res;
}
int prev_val(node *&o,int v){node *l,*r;
	split(o,l,r,v-1);
	if(l==NULL)
		return -1;
	int res=find_by_order(l,l->siz);
	merge(o,l,r);
	return res;
}
int next_val(node *&o,int v){node *l,*r;
	split(o,l,r,v);
	if(r==NULL)
		return -1;
	int res=find_by_order(r,1);
	merge(o,l,r);
	return res;
}

int main(){srand(100000);
	int T;scanf("%d",&T);
	while(T--){int opt,x;scanf("%d%d",&opt,&x);
		if(opt==1)
			insert(rt,x);
		else if(opt==2)
			erase(rt,x);
		else if(opt==3)
			printf("%d\n",order_of_key(rt,x));
		else if(opt==4)
			printf("%d\n",find_by_order(rt,x));
		else if(opt==5)
			printf("%d\n",prev_val(rt,x));
		else
			printf("%d\n",next_val(rt,x));
	}
	return 0;
}

Python 3.6

from random import random

class treap:
	class node:
		def __init__(self,val=0,ls=None,rs=None)->None:
			self.val=val
			self.key=random()
			self.ls=ls
			self.rs=rs
			self.siz=1
		def upd(self):
			self.siz=1
			if self.ls:
				self.siz+=self.ls.siz
			if self.rs:
				self.siz+=self.rs.siz
	def __init__(self)->None:
		self.root=None
	def __merge(self,l,r)->None:
		if not l:
			return r
		if not r:
			return l
		if l.keyNone:
		if not o:
			return None,None
		if o.val<=v:
			o.rs,tr=self.__split(o.rs,v)
			o.upd()
			return o,tr
		else:
			tr,o.ls=self.__split(o.ls,v)
			o.upd()
			return tr,o
	def insert(self,v)->None:
		u=self.node(val=v)
		l,r=self.__split(self.root,v)
		l=self.__merge(l,u)
		self.root=self.__merge(l,r)
	def erase(self,v)->bool:
		l,r=self.__split(self.root,v)
		l,u=self.__split(l,v-1)
		if u==None:
			self.root=self.__merge(l,r)
			return False
		u=self.__merge(u.ls,u.rs)
		l=self.__merge(l,u)
		self.root=self.__merge(l,r)
		return True
	def __kth(self,o,v):
		if o==None:
			return None
		lsiz=0
		if o.ls:
			lsiz=o.ls.siz
		if v<=lsiz:
			return self.__kth(o.ls,v)
		elif v==lsiz+1:
			return o.val
		else:
			return self.__kth(o.rs,v-lsiz-1)
	def kth(self,v):
		return self.__kth(self.root,v)
	def rank(self,v):
		l,r=self.__split(self.root,v-1)
		res=1
		if l:
			res+=l.siz
		self.root=self.__merge(l,r)
		return res
	def prev(self,v):
		l,r=self.__split(self.root,v-1)
		if l==None:
			return None
		res=self.__kth(l,l.siz)
		self.root=self.__merge(l,r)
		return res
	def next(self,v):
		l,r=self.__split(self.root,v)
		if r==None:
			return None
		res=self.__kth(r,1)
		self.root=self.__merge(l,r)
		return res

if __name__=="__main__":
	T=int(input())
	tr=treap()
	opt=[None,tr.insert,tr.erase,tr.rank,tr.kth,tr.prev,tr.next]
	for i in range(T):
		expr=list(map(int,input().split()))
		if expr[0]>=3:
			print(opt[expr[0]](expr[1]))
		else:
			opt[expr[0]](expr[1])

Java 8

咕咕咕。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前名称：数据结构8——无旋Treap-创新互联
文章源于：http://azwzsj.com/article/dspice.html