Treap
小柯
2020-05-05 17:36:37
~~~
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int n;
int opt,x;
class BST{
public:
int
protected:
struct {
int valu,pri,he;
int l,r,cnt,size;
}a[100005];
int rt,tot;
void up(int u){
a[u].size=a[a[u].l].size+a[a[u].r].size+a[u].cnt;
a[u].he=max(a[a[u].l].he,a[a[u].r].he)+1;
}
/*
。
/ \
。 。
/ \
。 。
*/
void leftrotate(int &u){
int k=a[u].r;
a[u].r=a[k].l;
a[k].l=u;
up(u),up(k),u=k;
}
/*
。
/ \
。 。
/ \
。 。
*/
void rightrotate(int &u){
int k=a[u].l;
a[u].l=a[k].r;
a[k].r=u;
up(u),up(k),u=k;
}
void _add(int &u,int valu){
if(!u)return(void)(u=++tot,a[u].size=a[u].cnt=1,a[u].pri=rand());
if(a[u].valu==valu)return(void)(++a[u].cnt,++a[u].size);
if(a[u].valu<valu)_add(a[u].l,valu);
if(valu<a[u].valu)_add(a[u].r,valu);
//if(a[a[u].l].he<a[a[u].r].he)leftrotate(u);
//if(a[a[u].r].he<a[a[u].l].he)rightrotate(u);
if(a[a[u].l].pri<a[a[u].r].pri)if(a[u].pri<a[a[u].r].pri)leftrotate(u);
else if(a[u].pri<a[a[u].l].pri)rightrotate(u);
return up(u);
}
void _erase(int &u,value){
if(a[u].valu==valu){
if(a[u].cnt>1)return(void)(--a[u].cnt);
if(!a[u].l||!a[u].r)return(void)(u=a[u].l+a[u].r);
if(a[a[u].l].valu<a[a[u].r].valu)leftrotate(u),_erase(a[u].l);
else rightrotate(u),_erase(a[u].r);
}
else if(a[u].valu<valu)_erase(a[u].l,valu);
else _erase(a[u].r,valu);
up(u);
}
int _queryRankByValue(int valu){
int u=rt,ans=0;
while(u){
if(a[u].valu==valu)return ans+1;
if(a[u].valu<valu)u=a[u].l;
else ans+=a[a[u].l].size+a[u].cnt,u=a[u].r;
}
return ans;
}
int _queryValueByRank(int rank){
int u=rt;
while(1){
if(rank<a[a[u].l].size)u=a[u].l;
else if(rank<=a[a[u].l].size+a[u].cnt)return u;
else k-=a[a[u].l].size+a[u].cnt,u=a[u].r;
}
}
int _queryPre(int valu)
};
int main(){
return 0;
}
~~~