NOI 2004 郁闷的出纳员 Splay

网址：http://www.lydsy.com/JudgeOnline/problem.php?id=1503

所有的操作都比较简单，而对于调整工资，就必须思考下，不过也简单，直接变成调整界限，和新来员工工资即可，剩下的就是splay。。。

/**************************************************************
    Problem: 1503
    User: h6363817
    Language: C++
    Result: Accepted
    Time:992 ms
    Memory:3228 kb
****************************************************************/
 
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mm=100020;
const int oo=2e9;
struct SplayTree
{
    int son[mm][2],far[mm],val[mm],sum[mm];
    int rt,size;
    void PushUp(int x)
    {
        sum[x]=sum[son[x][0]]+sum[son[x][1]]+1;
    }
    void Link(int x,int y,int c)
    {
        far[x]=y,son[y][c]=x;
    }
    void Rotate(int x,int c)
    {
        int y=far[x];
        Link(x,far[y],son[far[y]][1]==y);
        Link(son[x][!c],y,c);
        Link(y,x,!c);
        PushUp(y);
    }
    void Splay(int x,int g)
    {
        for(; far[x]!=g;)
        {
            int y=far[x],cx=(son[y][1]==x),cy=(son[far[y]][1]==y);
            if(far[y]==g)Rotate(x,cx);
            else
            {
                if(cx==cy)Rotate(y,cy);
                else Rotate(x,cx);
                Rotate(x,cy);
            }
        }
        PushUp(x);
        if(!g)rt=x;
    }
    void NewNode(int y,int &x,int a)
    {
        x=++size;
        far[x]=y,val[x]=a,sum[x]=1;
        son[x][0]=son[x][1]=0;
    }
    void Insert(int a)
    {
        int x=rt;
        while(son[x][val[x]<a])x=son[x][val[x]<a];
        NewNode(x,son[x][val[x]<a],a);
        Splay(size,0);
    }
    void Prepare()
    {
        NewNode(size=0,rt,-oo);
        NewNode(rt,son[rt][1],oo);
        sum[rt]=2;
    }
    int Suc(int a)
    {
        int x=rt,ret=oo;
        while(x)
        {
            if(val[x]==a) return a;
            if(val[x]>a) ret=min(ret,val[x]);
            x=son[x][val[x]<a];
        }
        return ret;
    }
    int Pre(int a)
    {
        int x=rt,ret=-oo;
        while(x)
        {
            if(val[x]==a)return a;
            if(val[x]<a)ret=max(ret,val[x]);
            x=son[x][val[x]<a];
        }
        return ret;
    }
    int Find(int a)
    {
        int x=rt,ans=0;
        while(x)
        {
            if(val[x]==a) ans=x;
            x=son[x][val[x]<a];
        }
        return ans;
    }
    int Select(int k,int g)
    {
        int x=rt;
        while(sum[son[x][1]]!=k)
        {
            if(sum[son[x][1]]>k) x=son[x][1];
            else k-=(sum[son[x][1]]+1),x=son[x][0];
        }
        Splay(x,g);
        return val[x];
    }
    int Delete(int a)
    {
        int x=Find(a),ans=0;
        if(x)
        {
            Splay(1,0);
            Splay(x,1);
            ans=sum[son[x][0]];
            son[x][0]=0;
            Splay(x,0);
        }
        return ans;
    }
} spt;
int main()
{
    int n,m,w,a,ans;
    char s[5];
    while(~scanf("%d%d",&n,&m))
    {
        spt.Prepare();
        w=ans=0;
        while(n--)
        {
            scanf("%s%d",s,&a);
            if(s[0]=='I')
            {
                a-=w;
                if(a>=m-w) spt.Insert(a);
            }
            if(s[0]=='A') w+=a;
            if(s[0]=='S') w-=a,ans+=spt.Delete(spt.Suc(m-w));
            if(s[0]=='F')
            {
                if(spt.sum[spt.rt]<a+2) puts("-1");
                else printf("%d\n",spt.Select(a,0)+w);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}