treap平衡树
- 格式：wps
- 大小：26.50 KB
- 文档页数：4
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define N 201000
int l[N],r[N],v[N],hr[N],s[N];
int n,root,m;
namespace TREAP
{
inline void l_rotate(int & x){
int y =r[x];
r[x] = l[x];
l[y] = x;
s[y] = s[x];
s[x] = s[l[x]] + s[r[x]] + 1;
x = y;
return;
}
inline void r_rotate(int & x){
int y = l[x];
l[x] = r[x];
r[y] = x;
s[y] = s[x];
s[x] = s[l[x]] + s[r[x]] + 1;
x = y;
return;
}
void insert(int & k,int & key){
if (k == 0){
v[++m] = key;
s[m] = 1;
hr[m] = rand();
k = m;
return;
}
s[k]++;
if (key <= v[k]){
insert(l[k],key);
if (hr[l[k]] > hr[k]){
r_rotate(k);
}
return;
}
if (key > v[k]){
insert(r[k],key);
if (hr[r[k]] > hr[k]) l_rotate(k);
return;
}
return;
}
int del(int & k,int key){
int ans;
s[k]--;
if (key == v[k] || !l[k] && key<=v[k] || r[k] == 0 && key > v[k]){
ans = v[k];
if (!l[k] || !r[k]){
k = l[k] + r[k];
return ans;
}
v[k] = del(l[k],key+1);
return ans;
}
if (key <= v[k]) return del(l[k],key);
if (key > v[k]) return del(r[k],key);
}
bool find(int & k,int &key){
if (k == 0) return 0;
if (key > v[k]) return find(r[k],key);
else return (v[k] == key || find(l[k],key));
}
int rank(int & t,int & key){
int ans;
if (t == 0) return 1;
if (key <= v[t]) return rank(l[t],key);
else return s[l[t]] + 1 + rank(r[t],key);
}
int sel(int & t,int k){
if (k == s[l[t]]+1) return v[t];
if (k<=s[l[t]]) return sel(l[t],k);
else return sel(r[t],k-1-s[l[t]]);
}
int pred(int & t,int & key){
if (t == 0) return key;
if (key <= v[t]) return pred(l[t],key);
else{
int ans = pred(r[t],key);
if (ans == key) ans = v[t];
return ans;
}
}
int succ(int &t,int & key){
if (t == 0) return key;
if (v[t]<=key) return succ(r[t],key);
else{
int ans = succ(l[t],key);
if (ans == key) ans = v[t];
return ans;
}
}
}
inline void order(){
int a,b;
scanf("%d%d",&a,&b);
switch(a){
case 1:TREAP::insert(root,b);break;
case 2:TREAP::del(root,b);break;
case 3:printf("%d\n",TREAP::find(root,b));break;
case 4:printf("%d\n",TREAP::rank(root,b));break;
case 5:printf("%d\n",TREAP::sel(root,b));break;
case 6:printf("%d\n",TREAP::pred(root,b));break;
case 7:printf("%d\n",TREAP::succ(root,b));break;
}
return;
}
int main(){
srand(unsigned(time(0)));
scanf("%d",&n);
m = 0;
while (n--){
order();
}
return 0;
}
