{"id":63,"date":"2010-01-02T15:27:00","date_gmt":"2010-01-02T07:27:00","guid":{"rendered":"http:\/\/localhost\/?p=63"},"modified":"2010-01-02T15:27:00","modified_gmt":"2010-01-02T07:27:00","slug":"spoj_3273_orderset","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=63","title":{"rendered":"SPOJ 3273 ORDERSET"},"content":{"rendered":"

\u5c31\u662f\u6807\u51c6\u7684\u5e73\u8861\u4e8c\u53c9\u6570\u3002\u3002
\u6709insert,delete,rank,select\u56db\u4e2a\u64cd\u4f5c\u3002\u3002
\u6211\u7528splay\u5c31\u662f\u8d85\u65f6\u3002\u3002\u3002\u5988\u5440\u3002\u3002\u6700\u540e\u7528\u522b\u4eba\u7684SBT\u8fc7\u6389\u4e86\u3002\u3002
Code:
#include<cstdio>
using namespace std;
const int inf=~0U>>1;
class splay
{
struct node
{
int k,s;
bool d;
node*c[2],*p;
void sc(node*_c,bool d)
{c[d]=_c;_c->p=this;_c->d=d;}
}*root,*Null,*Now,*stack[100000],Data[200000],*tmp;
int top;
typedef node* Node;
Node new_node(int k)
{
if(top) tmp=stack[–top];
else tmp=Now++;
tmp->k=k;tmp->s=1;
tmp->c[0]=tmp->c[1]=Null;
return tmp;
}
void del_node(Node p)
{
stack[top++]=p;
}
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(int k)
{
int r;
for(Node t=root->c[1];;)
{
r=t->c[0]->s;
if(r==k) return t;
t=t->c[k>r];
if(k>r) k-=r+1;
}
}
Node ser(Node t,int k)
{
for(;t!=Null&&t->k!=k;t=t->c[k>t->k]);
return t;
}
Node insert(int k)
{
bool d;Node t=root;
for(;t->k!=k;)
{
d=k>t->k;
if(t->c[d]==Null)
{
Node p=new_node(k);
t->sc(p,d);
}
t=t->c[d];
}
return t;
}
int rank(int k)
{
int ans=0;
for(Node t=root->c[1];t!=Null;)
{
if(k>t->k) ans+=1+t->c[0]->s;
t=t->c[k>t->k];
}
return ans;
}
public:
splay()
{
top=0;Now=Data;
Null=new_node(0);Null->s=0;
root=new_node(-inf);root->p=root;
}
void ins(int x)
{
Node p=insert(x);
spl(p,root);
}
int sel(int x)
{
if(x>=root->c[1]->s) return inf;
Node p=select(x);
return p->k;
}
int ran(int x)
{
return rank(x);
}
void del(int k)
{
Node tmp=ser(root->c[1],k);if(tmp==Null) return;
while(tmp->c[0]!=Null)
rot(tmp->c[0]);
if(tmp->c[1]==Null)
{
tmp->p->c[tmp->d]=Null;
tmp->p->s–;
spl(tmp->p,root);
del_node(tmp);
return;
}
tmp->p->sc(tmp->c[1],tmp->d);
spl(tmp->c[1],root);
del_node(tmp);
}
}*sp;
int main()
{
int n,t,a;char c;sp=new splay;scanf("%dn",&n);char C[1000];
for(int i=0;i<n;i++)
{
scanf("%c %dn",&c,&t);
switch(c)
{
case ‘I’:sp->ins(t);break;
case ‘D’:sp->del(t);break;
case ‘K’:a=sp->sel(t-1);
if(a==inf) puts("invalid");
else printf<\/a>("%dn",a);break;
case ‘C’:printf<\/a>("%dn",sp->ran(t));break;
}
}
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u5c31\u662f\u6807\u51c6\u7684\u5e73\u8861\u4e8c\u53c9\u6570\u3002\u3002\u6709insert,delete,rank,select\u56db\u4e2a\u64cd\u4f5c\u3002\u3002\u6211\u7528splay\u5c31\u662f\u8d85\u65f6\u3002\u3002\u3002\u5988\u5440\u3002\u3002\u6700\u540e\u7528\u522b\u4eba\u7684SBT\u8fc7\u6389\u4e86\u3002\u3002Code:#include<cstdio>using namespace std;const int inf=~0U>>1;class splay{ struct node { int k,s; bool d; node*c[2],*p; void sc(node*_c,bool d) {c[d]=_c;_c->p=this;_c->d=d;} }*root,*Null,*Now,*stack[100000],Data[200000],*tmp; int top; typedef node* Node; Node new_node(int k) { if(top) tmp=stack[–top]; else tmp=Now++; tmp->k=k;tmp->s=1; tmp->c[0]=tmp->c[1]=Null; return tmp; } void del_node(Node p) { stack[top++]=p; } 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>\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\/63"}],"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=63"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/63\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=63"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=63"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=63"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}