{"id":59,"date":"2009-12-31T19:41:00","date_gmt":"2009-12-31T11:41:00","guid":{"rendered":"http:\/\/localhost\/?p=59"},"modified":"2009-12-31T19:41:00","modified_gmt":"2009-12-31T11:41:00","slug":"splay","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=59","title":{"rendered":"Splay"},"content":{"rendered":"

\u8d5e\u8d5e\u963f\u3002\u3002
Splay\u7edd\u5bf9\u662f\u6700\u5b8c\u7f8e\u7684\u5e73\u8861\u6811\u3002\u3002\u9664\u4e86\u65f6\u95f4\u6bd4\u8f83\u6162\u3002\u3002\u5176\u4ed6\u7edd\u5bf9\u662f\u6700NB\u7684\u3002\u3002
\u60f3\u51fa\u8fd9\u73a9\u610f\u7684\u4eba\u7edd\u5bf9\u662f\u5929\u624d\u4e2d\u7684\u5929\u624d\u3002\u3002\u3002
\u5199\u4e86\u4e2aCode\u3002\u3002\u8d34\u4e00\u4e0b\u3002\u3002
#include<cstdio>
#include<iostream>
using namespace std;
const int inf=~0U>>1;
class splay
{
struct node
{
int k,s;\/\/k\u662f\u503c,s\u662f\u5b50\u6811\u5927\u5c0f
bool d;\/\/d\u662f\u8be5\u8282\u70b9\u662f\u7236\u4eb2\u7684\u90a3\u79cd\u8282\u70b9
node*c[2],*p;\/\/c[0]\u3001c[1]\u5206\u522b\u662f\u5de6\uff0c\u53f3\u5b69\u5b50\uff0cp\u662f\u7236\u4eb2
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<\/a>("%dn",sp->sel(a));
}
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u8d5e\u8d5e\u963f\u3002\u3002Splay\u7edd\u5bf9\u662f\u6700\u5b8c\u7f8e\u7684\u5e73\u8861\u6811\u3002\u3002\u9664\u4e86\u65f6\u95f4\u6bd4\u8f83\u6162\u3002\u3002\u5176\u4ed6\u7edd\u5bf9\u662f\u6700NB\u7684\u3002\u3002\u60f3\u51fa\u8fd9\u73a9\u610f\u7684\u4eba\u7edd\u5bf9\u662f\u5929\u624d\u4e2d\u7684\u5929\u624d\u3002\u3002\u3002\u5199\u4e86\u4e2aCode\u3002\u3002\u8d34\u4e00\u4e0b\u3002\u3002#include<cstdio>#include<iostream>using namespace std;const int inf=~0U>>1;class splay{ struct node { int k,s;\/\/k\u662f\u503c,s\u662f\u5b50\u6811\u5927\u5c0f bool d;\/\/d\u662f\u8be5\u8282\u70b9\u662f\u7236\u4eb2\u7684\u90a3\u79cd\u8282\u70b9 node*c[2],*p;\/\/c[0]\u3001c[1]\u5206\u522b\u662f\u5de6\uff0c\u53f3\u5b69\u5b50\uff0cp\u662f\u7236\u4eb2 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/59"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=59"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/59\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=59"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=59"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=59"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}