BZOJ 3224: Tyvj 1728 普通平衡树 题解
2018-10-02 本文已影响0人
AmadeusChan
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3224
思路：裸平衡树，直接模拟即可。
代码（SBT）：
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
struct node {
node *left,*right;
int key,s;
};
node *roof,*bank=new(node);
int n;
int left_ratote(node* &t){
node *k=(*t).right;
(*t).right=(*k).left;
(*t).s=(*(*t).left).s+(*(*t).right).s+1;
(*k).left=t;
(*k).s=(*t).s+(*(*k).right).s+1;
t=k;
return 0;
}
int right_ratote(node* &t){
node *k=(*t).left;
(*t).left=(*k).right;
(*t).s=(*(*t).left).s+(*(*t).right).s+1;
(*k).right=t;
(*k).s=(*(*k).left).s+(*t).s+1;
t=k;
return 0;
}
int maintain(node* &t){
if ((*(*(*t).left).left).s>(*(*t).right).s){
right_ratote(t);
maintain((*t).right);
maintain(t);
return 0;
}
if ((*(*(*t).left).right).s>(*(*t).right).s){
left_ratote((*t).left);
right_ratote(t);
maintain((*t).left);
maintain((*t).right);
maintain(t);
return 0;
}
if ((*(*(*t).right).right).s>(*(*t).left).s){
left_ratote(t);
maintain((*t).left);
maintain(t);
return 0;
}
if ((*(*(*t).right).left).s>(*(*t).left).s){
right_ratote((*t).right);
left_ratote(t);
maintain((*t).left);
maintain((*t).right);
maintain(t);
return 0;
}
return 0;
}
int INSERT(int key,node* &t){
if (t==bank){
t=new(node);
(*t).key=key;
(*t).s=1;
(*t).left=(*t).right=bank;
return 0;
}
(*t).s++;
if (key<=(*t).key){
INSERT(key,(*t).left);
} else INSERT(key,(*t).right);
maintain(t);
return 0;
}
int DELETE(int key,node* &t){
if (key==(*t).key){
if ((*t).left==bank){
if ((*t).right==bank){
delete(t);
t=bank;
return 0;
} else {
node *p=(*t).right;
delete(t);
t=p;
return 0;
}
} else {
if ((*t).right==bank){
node *p=(*t).left;
delete(t);
t=p;
return 0;
}
}
if (rand()%2){
left_ratote(t);
DELETE(key,(*t).left);
} else {
right_ratote(t);
DELETE(key,(*t).right);
}
} else {
if (key<(*t).key){
DELETE(key,(*t).left);
} else DELETE(key,(*t).right);
}
(*t).s=(*(*t).left).s+(*(*t).right).s+1;
maintain(t);
return 0;
}
int get_rank(int key,node *t){
int rec=0;
node *p=t;
while (p!=bank){
if ((*p).key<key){
rec+=((*(*p).left).s+1);
p=(*p).right;
} else {
p=(*p).left;
}
}
return rec;
}
int get_num(int key,node *t){
if ((key-1)==(*(*t).left).s){
return (*t).key;
}
if ((key-1)<(*(*t).left).s){
return get_num(key,(*t).left);
} else {
return get_num(key-(*(*t).left).s-1,(*t).right);
}
}
int get_prefix(int key,node *t){
if (t==bank){
return -0x7fffffff;
}
if ((*t).key<key){
return max((*t).key,get_prefix(key,(*t).right));
} else {
return get_prefix(key,(*t).left);
}
}
int get_suffix(int key,node *t){
if (t==bank){
return 0x7fffffff;
}
if (key<(*t).key){
return min((*t).key,get_suffix(key,(*t).left));
} else {
return get_suffix(key,(*t).right);
}
}
int main(){
srand(0);
roof=(*bank).left=(*bank).right=bank;
(*bank).s=0;
scanf("%d",&n);
while (n--){
int x,y;
scanf("%d%d",&x,&y);
switch (x){
case 1:
INSERT(y,roof);
break;
case 2:
DELETE(y,roof);
break;
case 3:
printf("%d\n",get_rank(y,roof)+1);
break;
case 4:
printf("%d\n",get_num(y,roof));
break;
case 5:
printf("%d\n",get_prefix(y,roof));
break;
case 6:
printf("%d\n",get_suffix(y,roof));
break;
}
}
return 0;
}
