treap
treapと書きました..やっと過ぎた.の
まず再帰版の非class版の練習手を書いて、数日後にclassをテンプレートにします
treap=tree+heap
それぞれに対して、キー値keyが与えられ、このBSTはBSTの性質を維持しながらkey上でもheapの性質を維持することが要求され、これにより大きなチェーンの状況を防止することができる.
回転と正常の差は多くありません.の
SPOJ 3273で4 s+[SPOJは遅いですね..]
まず再帰版の非class版の練習手を書いて、数日後にclassをテンプレートにします
treap=tree+heap
それぞれに対して、キー値keyが与えられ、このBSTはBSTの性質を維持しながらkey上でもheapの性質を維持することが要求され、これにより大きなチェーンの状況を防止することができる.
回転と正常の差は多くありません.の
SPOJ 3273で4 s+[SPOJは遅いですね..]
#include
#include
#include
#include
#include
#include
using namespace std;
struct node{
node *lson,*rson;
int value,key,size;
node(int v) :value(v),key(rand()),size(1),lson(NULL),rson(NULL){};
void maintain(){
if (!this) return;
size=1;
if (lson!=NULL) size+=lson->getsize();
if (rson!=NULL) size+=rson->getsize();
}
int getsize(){
return this?size:0;
}
};
inline void rotate_l(node* &root){
node* tmp=root->rson;
root->rson=tmp->lson;
tmp->lson=root;
tmp->maintain();
root->maintain();
root=tmp;
}
inline void rotate_r(node* &root){
node* tmp=root->lson;
root->lson=tmp->rson;
tmp->rson=root;
tmp->maintain();
root->maintain();
root=tmp;
}
inline void forever(node* &root,const int &value){
if (root==NULL){
root=new node(value);
return;
}
if (value==root->value) return;
if (valuevalue){
forever(root->lson,value);
if (root->lson->key>root->key)
rotate_r(root);
}
else{
forever(root->rson,value);
if (root->rson->key>root->key)
rotate_l(root);
}
root->maintain();
}
inline void forget(node* &root,const int &value){
if (root==NULL) return;
if (value==root->value){
if (root->lson && root->rson){
if (root->lson->key>root->rson->key){
rotate_r(root);
forget(root->rson,value);
}
else{
rotate_l(root);
forget(root->lson,value);
}
}
else{
node* tmp=root;
root=root->rson?root->rson:root->lson;
delete tmp;
return;
}
}
else
if (valuevalue)
forget(root->lson,value);
else
forget(root->rson,value);
root->maintain();
}
inline node* kth(node* root,int k){
if (root==NULL) return NULL;
int tmp=root->lson->getsize();
if (k-1==tmp)
return root;
else
if ((k-1)lson,k);
else
return kth(root->rson,k-tmp-1);
}
inline int rank(node* root,const int &value){
if (root==NULL) return 0;
int tmp=root->lson->getsize();
if (value==root->value)
return tmp+1;
else
if (valuevalue)
return rank(root->lson,value);
else
return rank(root->rson,value)+tmp+1;
}
node *root;
int n,t;
char a,str[20];
inline void write(int k){
if (k>root->getsize())
printf("invalid
");
else
printf("%d
",kth(root,k)->value);
}
int main(){
freopen("treap.in","r",stdin);
freopen("treap.out","w",stdout);
srand(unsigned(time));
scanf("%d
",&n);
for (int i=1;i<=n;i++){
scanf("%s%d",str,&t);
// cout<getsize()<