[NOI2004 郁闷的出纳员]我的第一个Splay

【算法分析】

以前用SBT做过了，不过为了学习Splay，又用它来做测试了。。。

第一次写Splay，先写了个非指针版的。。。一直WA，后来模范beyondvoid大牛的一些技巧，写了个指针版的才AC。。。

【其它】

居然比SBT快。。。

不过SBT以前用pascal写的，现在是C++，另外我觉得我的SBT使用递归也是一个重要原因吧。

【CODE】

#include const int inf=1000000000;
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                           else q->r=p;
                break;
            }else
            if (key                q=p;
                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                    root->l=q->r;
                    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 ‘A’:ss+=x; Splay.del(); break;
            case ‘S’:ss-=x; Splay.del(); break;
            case ‘F’:printf("%dn",Splay.get(x+1)); break;
        }   
    }   
    printf("%dn",innum-Splay.root->s);
}