「题解」「NOI2004」郁闷的出纳员 cashier

题目链接:Luogu P1486/BZOJ 1503/LibreOJ 10145/NOI2004 D1T1。

一道比较简单的 $\text{Splay}$ 模板题,需要一定的思考。


题目

题意简述

第一行有两个非负整数 $n$ 和 $\text{min}$。$n$ 表示下面有多少条命令,$\min$ 表示工资下界。

接下来的 $n$ 行,每行表示一条命令。命令可以是以下四种之一:

名称格式作用
I 命令I k新建一个工资档案,初始工资为 $k$。如果某员工的初始工资低于工资下界,他将立刻离开公司。
A 命令A k把每位员工的工资加上 $k$。
S 命令S k把每位员工的工资扣除 $k$。
F 命令F k查询第 $k$ 多的工资。

在初始时,可以认为公司里一个员工也没有。

数据范围

I命令的条数不超过 $10^5$;
AS 命令的总条数不超过 $100$;
F 命令的条数不超过 $10^5$;
每次工资调整的调整量不超过 $10^3$;
新员工的工资不超过 $10^5$。

时空限制

题目时间限制空间限制
Luogu P1486$$1\text{s}$$$$125\text{MiB}$$
BZOJ 1503$$5\text{s}$$$$64\text{MiB}$$
LibreOJ 10145$$1\text{s}$$$$512\text{MiB}$$
NOI2004 D1T1$$1\text{s}$$$$?\text{MiB}$$

题解

思路

考虑用一个简单变量 $\text{delta}$ 来存储工资的变化量,再用 $\text{Splay}$ 维护每位员工的工资的剩余部分,那么 $\text{Splay}$ 中节点编号为 $x$ 的员工的工资就是 $\text{val}_x+\text{delta}$。

那么对于每种操作:

  • I k
    先判断 $k$ 和 $\min$ 的关系,决定是否插入,然后再往 $\text{Splay}$ 里插入 $k-\min$。
  • A k
    直接将 $\text{delta}$ 加上 $k$ 即可。
  • S k
    先往 $\text{Splay}$ 里插入 $\min-\text{delta}$,那么将要被赶走的员工数量为 $\operatorname{rank}(\min-\text{delta})-1$,注意这里需要提前插入哨兵节点,所以要减掉 $1$。
  • F k
    直接查询即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F //定义正无穷
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) //fread() 快读
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){ //快读
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,Min;

inline void Read(void){
    n=read(),Min=read();
    return;
}

struct Splay{ //Splay 文艺平衡树的模板
    int tot;
    int root;
    int fa[MAXN];
    int ch[MAXN][2];
    int val[MAXN],cnt[MAXN],size[MAXN];
    inline void maintain(reg int x){
        size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
        return;
    }
    inline bool get(reg int x){
        return x==ch[fa[x]][1];
    }
    inline void clear(reg int x){
        fa[x]=ch[x][0]=ch[x][1]=0;
        val[x]=cnt[x]=size[x]=0;
        return;
    }
    inline void rotate(reg int x){
        reg int f=fa[x],ff=fa[f];
        reg bool w=get(x);
        ch[f][w]=ch[x][w^1];
        fa[ch[f][w]]=f;
        fa[f]=x;
        fa[x]=ff;
        ch[x][w^1]=f;
        if(ff)
            ch[ff][ch[ff][1]==f]=x;
        maintain(x);
        maintain(f);
        return;
    }
    inline void splay(reg int x,reg int goal){
        for(reg int qwq;(qwq=fa[x])!=goal;rotate(x))
            if(fa[qwq]!=goal)
                rotate(get(x)==get(qwq)?qwq:x);
        if(goal==0)
            root=x;
        return;
    }
    inline void insert(reg int x){
        if(!root){
            val[++tot]=x;
            ++cnt[tot];
            root=tot;
            maintain(root);
            return;
        }
        reg int ID=root,f=0;
        while(true){
            if(val[ID]==x){
                ++cnt[ID];
                maintain(ID);
                maintain(f);
                splay(ID,0);
                break;
            }
            f=ID;
            ID=ch[ID][val[ID]<x];
            if(!ID){
                val[++tot]=x;
                ++cnt[tot];
                fa[tot]=f;
                ch[f][val[f]<x]=tot;
                root=tot;
                maintain(tot);
                maintain(f);
                splay(tot,0);
                return;
            }
        }
        return;
    }
    inline int id(reg int x){
        reg int ID=root;
        while(true){
            if(x==val[ID])
                return ID;
            else{
                if(x<val[ID])
                    ID=ch[ID][0];
                else
                    ID=ch[ID][1];
            }
        }
    }
    inline int rank(reg int x){
        reg int res=0,ID=root;
        while(true){
            if(x<val[ID])
                ID=ch[ID][0];
            else{
                res+=size[ch[ID][0]];
                if(x==val[ID]){
                    splay(ID,0);
                    return res+1;
                }
                res+=cnt[ID];
                ID=ch[ID][1];
            }
        }
        return -1;
    }
    inline int kth(reg int x){
        reg int ID=root;
        while(true){
            if(ch[ID][0]&&x<=size[ch[ID][0]]){
                ID=ch[ID][0];
            }
            else{
                x-=cnt[ID]+size[ch[ID][0]];
                if(x<=0)
                    return val[ID];
                ID=ch[ID][1];
            }
        }
        return -INF;
    }
    inline int pre(void){
        reg int ID=ch[root][0];
        while(ch[ID][1])
            ID=ch[ID][1];
        return ID;
    }
    inline int nxt(void){
        reg int ID=ch[root][1];
        while(ch[ID][0])
            ID=ch[ID][0];
        return ID;
    }
    inline void del(reg int k){
        rank(k);
        if(cnt[root]>1){
            --cnt[root];
            maintain(root);
            return;
        }
        if(!ch[root][0]&&!ch[root][1]){
            clear(root);
            root=0;
            return;
        }
        if(!ch[root][0]){
            reg int ID=root;
            root=ch[root][1];
            fa[root]=0;
            clear(ID);
            return;
        }
        if(!ch[root][1]){
            reg int ID=root;
            root=ch[root][0];
            fa[root]=0;
            clear(ID);
            return;
        }
        reg int x=pre(),ID=root;
        splay(x,0);
        fa[ch[ID][1]]=x;
        ch[x][1]=ch[ID][1];
        clear(ID);
        maintain(root);
        return;
    }
};

int delta; //记录变化量
Splay S;

inline void Work(void){
    S.insert(-INF),S.insert(INF); //插入哨兵节点
    reg int cnt=0; //统计插入的节点数量。
    while(n--){
        static char ch;
        static int k;
        do
            ch=getchar();
        while(ch<'A'||'Z'<ch);
        k=read();
        switch(ch){
            case 'I':
                if(k>=Min){
                    S.insert(k-delta);
                    ++cnt; //这题有点玄学
                }
                break;
            case 'A':{
                delta+=k;
                break;
            }
            case 'S':{
                delta-=k;
                S.insert(Min-delta);
                reg int a=S.id(-INF),b=S.id(Min-delta);
                S.splay(a,0);
                S.splay(b,a);
                S.ch[S.ch[S.root][1]][0]=0;
                S.del(Min-delta);
                break;
            }
            case 'F':{
                reg int temp=S.rank(INF)-2;
                if(temp<k)
                    puts("-1");
                else
                    printf("%d\n",S.kth(temp+2-k)+delta);
                break;
            }
            default:break;
        }
    }
    reg int temp=S.rank(INF)-2;
    printf("%d\n",cnt-temp);
    return;
}