AC日记——郁闷的出纳员 codevs 1286

郁闷的出纳员

思路：

　　设工资下限为ko，然后ko--（因为要小于工资下限）；

　　设cur为记录工资增长，降低；

　　设第i个人的工资为pos；

　　对应的四种操作：

　　　　插入：cur-pos-ko；

　　　　增长：cur-=pos；

　　　　降低：cur+=pos；

　　　　　　每个降低操作都要进行一次删除节点；

　　　　　　把小于等于cur的节点全部删掉；

　　　　排名：输出rank（）-cur+ko；

　　splay支持以上全部操作；

　　还有一点，如果一开始这个人的工资小于ko，则不算在离去的人里；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 1000005

struct TreeNodeType {

    int w,key,opi,size,ch[];

    void destroy()

    {

        w=key=opi=size=ch[]=ch[]=;

    }

    void create(int x)

    {

        key=x;

        w=size=;

        opi=ch[]=ch[]=;

    }

};

struct TreeNodeType tree[maxn<<];

int n,ko,root,tot,cur,ans,tot_;

inline void in(int &now)

{

    register char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline int getson(int now)

{

    return tree[tree[now].opi].ch[]==now;

}

inline void updata(int now)

{

    tree[now].size=tree[now].w;

    if(tree[now].ch[]) tree[now].size+=tree[tree[now].ch[]].size;

    if(tree[now].ch[]) tree[now].size+=tree[tree[now].ch[]].size;

}

inline void rotate(int now)

{

    int opi=tree[now].opi,fopi=tree[opi].opi,pos=getson(now);

    if(tree[tree[now].ch[pos^]].opi)tree[tree[now].ch[pos^]].opi=opi;

    tree[opi].ch[pos]=tree[now].ch[pos^];

    if(fopi) tree[fopi].ch[getson(opi)]=now;

    tree[opi].opi=now;tree[now].opi=fopi;

    tree[now].ch[pos^]=opi;

    updata(opi),updata(now);

}

void splay(int now)

{

    for(int opi;opi=tree[now].opi;rotate(now))

    {

        if(tree[opi].opi) rotate(getson(now)==getson(opi)?opi:now);

    }

    root=now;

}

void insert(int x)

{

    if(!root) tree[++tot].create(x),root=tot;

    else

    {

        int now=root,opi=;

        while()

        {

            if(tree[now].key==x)

            {

                tree[now].w++;

                tree[now].size++;

                splay(now);

                break;

            }

            opi=now,now=tree[now].ch[x>tree[now].key];

            if(!now)

            {

                tot++;

                tree[tot].create(x);

                tree[tot].opi=opi;

                tree[opi].ch[x>tree[opi].key]=tot;

                splay(tot);break;

            }

        }

    }

}

void del()

{

    ans+=tree[root].size-;

    if(!tree[root].ch[]) tree[].destroy(),root=;

    else

    {

        int tmp=root;

        root=tree[root].ch[];

        tree[tmp].destroy();

        tree[root].opi=;

        ans-=tree[root].size;

    }

}

int rank(int x)

{

    int now=root;

    while()

    {

        if(tree[now].ch[])

        {

            if(x>tree[tree[now].ch[]].size) x-=tree[tree[now].ch[]].size;

            else

            {

                now=tree[now].ch[];

                continue;

            }

        }

        if(x<=tree[now].w)

        {

            splay(now);

            return tree[now].key;

        }

        else

        {

            x-=tree[now].w;

            now=tree[now].ch[];

        }

    }

}

int main()

{

    in(n),in(ko),ko--;

    char ch[];int pos;

    while(n--)

    {

        scanf("%s",ch);in(pos);

        if(ch[]=='I') if(pos>ko) insert(pos+cur-ko),tot_++;

        if(ch[]=='A') cur-=pos;

        if(ch[]=='S') cur+=pos,insert(cur),del();

        if(ch[]=='F')

        {

            if(tot_-ans>=pos) printf("%d\n",rank(tot_-ans-pos+)-cur+ko);

            else printf("-1\n");

        }

    }

    printf("%d\n",ans);

    return ;

}

巴特西

AC日记——郁闷的出纳员 codevs 1286

最新文章

热门文章