Treap
T r e a p = T r e e ( B S T ) + H e a p Treap=Tree(BST)+Heap Treap=Tree(BST)+Heap
能维护的:
- 插入 xx 数
- 删除 xx 数(若有多个相同的数,因只删除一个)
- 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1 )
- 查询排名为 xx 的数
- 求 xx 的前驱(前驱定义为小于 xx,且最大的数)
- 求 xx 的后继(后继定义为大于 xx,且最小的数)
P3369 【模板】普通平衡树
// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369#sub
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Date: 2021-02-25 15:47:20
// --------by Herio--------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
int sum=0,R=0;//sum (sum of node) R (root index)
int size[N],v[N],num[N],rd[N],son[N][2];
inline void pushup(int p){
size[p]=size[son[p][0]]+size[son[p][1]]+num[p];
}
inline void rotate(int &p,int d){ //d=0 (left rotate)
int k=son[p][d^1];
son[p][d^1]=son[k][d];
son[k][d]=p;
pushup(p),pushup(k),p=k;
}
void ins(int &p,int x){
if (!p){
p=++sum,size[p]=num[p]=1;
v[p]=x,rd[p]=rand();
return;
}
if (v[p]==x){
num[p]++,size[p]++;return;
}
int d=(x>v[p]);
ins(son[p][d],x);
if (rd[p]<rd[son[p][d]]) rotate(p,d^1);//Max Heap
pushup(p);
}
void del(int &p,int x){
if (!p) return;
if(x!=v[p]) del(son[p][x>v[p]],x);
else{
if (!son[p][0] && !son[p][1]){
num[p]--,size[p]--;
if (!num[p]) p=0;
}
else if (son[p][0] && !son[p][1]){
rotate(p,1);
del(son[p][1],x);
}
else if (!son[p][0] && son[p][1]){
rotate(p,0);
del(son[p][0],x);
}
else if (son[p][0] && son[p][1]){
int d=(rd[son[p][0]]>rd[son[p][1]]);
rotate(p,d);
del(son[p][d],x);
}
}
pushup(p);
}
int rk(int p,int x){
if (!p) return 0;
if (v[p]==x) return size[son[p][0]]+1;
if (v[p]<x) return size[son[p][0]]+num[p]+rk(son[p][1],x);
if (v[p]>x) return rk(son[p][0],x);
}
int find(int p,int x){
if (!p) return 0;
if (size[son[p][0]]>=x) return find(son[p][0],x);
else if (size[son[p][0]]+num[p]<x)
return find(son[p][1],x-num[p]-size[son[p][0]]);
else return v[p];
}
int pre(int p,int x){
if (!p) return -inf;
if (v[p]>=x) return pre(son[p][0],x);
else return max(v[p],pre(son[p][1],x));
}
int suc(int p,int x){
if (!p) return inf;
if (v[p]<=x) return suc(son[p][1],x);
else return min(v[p],suc(son[p][0],x));
}
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline T& read(T& r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
int main(){
int n;read(n);
for (int i=0;i<n;++i){
int opt,x;read(opt),read(x);
if (opt==1) ins(R,x);
else if (opt==2) del(R,x);
else if (opt==3) printf("%d\n",rk(R,x));
else if (opt==4) printf("%d\n",find(R,x));
else if (opt==5) printf("%d\n",pre(R,x));
else if (opt==6) printf("%d\n",suc(R,x));
}
return 0;
}
有旋 Treap 常数小
无选fhq Treap 常数较大。
https://www.luogu.com.cn/record/47117035