【算法分析】
以前用SBT做过了，不过为了学习Splay，又用它来做测试了。。。
第一次写Splay，先写了个非指针版的。。。一直WA，后来模范beyondvoid大牛的一些技巧，写了个指针版的才AC。。。
【其它】
居然比SBT快。。。
不过SBT以前用pascal写的，现在是C++，另外我觉得我的SBT使用递归也是一个重要原因吧。
【CODE】
#include
int limit,ss;
struct Splaytype{
struct Splaynode{
Splaynode *l,*r,*fa;
int key,s;
};
Splaynode space[1000000],*root,*p,*q,*null;
int tot;
void init(){
null=&space[0];
null->l=null;
null->r=null;
null->fa=null;
null->s=0;
tot=1;
Splaynode *p=&space[tot];
p->l=null;
p->r=null;
p->fa=null;
p->key=inf;
p->s=1;
root=p;
}
inline void update(Splaynode *x){
if (x==null) return;
x->s=x->l->s+x->r->s+1;
}
void zag(Splaynode *x){
Splaynode *y=x->fa;
y->r=x->l;
x->l=y;
if (y->fa->l==y) y->fa->l=x;
else y->fa->r=x;
x->fa=y->fa;
y->fa=x;
y->r->fa=y;
update(y);
update(x);
}
void zig(Splaynode *x){
Splaynode *y=x->fa;
y->l=x->r;
x->r=y;
if (y->fa->l==y) y->fa->l=x;
else y->fa->r=x;
x->fa=y->fa;
y->fa=x;
y->l->fa=y;
update(y);
update(x);
}
void Splay(Splaynode *x,Splaynode *pos){
if (x==root) return;
Splaynode *y,*z;
while (x->fa!=pos){
y=x->fa; z=y->fa;
if (z==pos)
if (y->l==x) zig(x);
else zag(x);
else if (z->l==y)
if (y->l==x) {zig(y); zig(x);}
else {zag(x); zig(x);}
else
if (y->r==x) {zag(y); zag(x);}
else {zig(x); zag(x);}
}
}
void ins(int key){
p=root->l,q=root;
for (;;){
if (p==null){
p=&space[++tot];
p->l=null;
p->r=null;
p->s=1;
p->key=key;
p->fa=q;
if (key
break;
}else
if (key
p=p->l;
}
else{
q=p;
p=p->r;
}
}
q=p;
for (;p!=null;p=p->fa) update(p);
Splay(q,root);
}
void del(){
p=root->l; q=root;
for (;;){
if (p==null){
Splay(q,root);
if (q->key+ss
if (q->r!=null) q->r->fa=root;
update(root);
}
else{
q->l=null;
update(q);
update(root);
}
return;
}else
if (p->key+ss>=limit){
q=p;
p=p->l;
}
else{
q=p;
p=p->r;
}
}
}
int get(int rank){
if (rank>root->s) return -1;
int done=0,td;
p=root;
for (;;){
if (done+p->r->s+1==rank) return p->key+ss;
if (done+p->r->s+1>rank) p=p->r;
else{
done+=p->r->s+1;
p=p->l;
}
}
}
}Splay;
int main(){
freopen("cashier.in","r",stdin);
freopen("cashier.out","w",stdout);
Splay.init();
int n,x,innum=1; char ch;
scanf("%d%d",&n,&limit);
for (int i=1;i<=n;i++){
for (ch=getchar();ch==’ ‘ || ch==’n’;ch=getchar());
scanf("%d",&x);
switch (ch){
case ‘I’:if (x
case ‘S’:ss-=x; Splay.del(); break;
case ‘F’:printf("%dn",Splay.get(x+1)); break;
}
}
printf("%dn",innum-Splay.root->s);
}
虽然说着比较牵强。。。
）
