Splay

赞赞阿。。
Splay绝对是最完美的平衡树。。除了时间比较慢。。其他绝对是最NB的。。
想出这玩意的人绝对是天才中的天才。。。
写了个Code。。贴一下。。
#include<cstdio>
#include<iostream>
using namespace std;
const int inf=~0U>>1;
class splay
{
struct node
{
int k,s;//k是值,s是子树大小
bool d;//d是该节点是父亲的那种节点
node*c[2],*p;//c[0]、c[1]分别是左,右孩子,p是父亲
node(int _k,node*_c):k(_k),s(1){c[0]=c[1]=_c;}
void sc(node*_c,bool d) //sc means set child
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now;
typedef node* Node;
void upd(Node t)
{
t->s=t->c[0]->s+t->c[1]->s+1;
}
void rot(Node t)
{
node*p=t->p;bool d=t->d;
p->sc(t->c[!d],d);
p->p->sc(t,p->d);
t->sc(p,!d);
upd(p);upd(t);
}
void spl(Node x,Node f)
{
while(x->p!=f)
{
if(x->p->p==f) rot(x);
else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );
}
}
Node select(Node t,int k)
{
int r;
for(;;)
{
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
Node insert(Node t,int k)
{
bool d=k>t->k;
if(t->c[d]==Null)
{
Node p=new node(k,Null);
t->sc(p,d);
return p;
}
return insert(t->c[d],k);
}
public:
splay()
{
Null=new node(0,0);Null->s=0;
root=new node(-inf,Null);
}
void ins(int x)
{
Node p=insert(root,x);
spl(p,root);
}
int sel(int x)
{
Node p=select(root->c[1],x);
spl(p,root);
return p->k;
}
}*sp;
int main()
{
freopen("in","r",stdin);
int n;int k,a;sp=new splay;cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d %d",&k,&a);
if(k==0)
sp->ins(a);
else
printf("%dn",sp->sel(a));
}
}

4 thoughts on “Splay

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>