题目大意

在一个公司中，有四种操作

1. 加入一个初始工资为$a$的员工

2. 将所有人工资提高一个数

3. 将所有人工资降低一个数

4. 询问第$k$多工资的员工是谁

若有某人的工资低于工资下限，就会立刻离开公司

数据范围

第一条命令的条数不超过100000，第二条和第三条命令的总条数不超过100，第四条命令的条数不超过100000

每次工资调整的调整量不超过1000，新员工的工资不超过100000

题解

splay是一个非常好理解的数据结构，拥有和平衡树类似的旋转功能

插入新节点后都把节点旋转到根节点，然后基本都是从左右子树出发执行操作

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for (int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
using namespace std;

int s[100500],f[100500],c[100500],t[100500][2];
int n,m,tot,root,result,delta;
inline void pushup(int x){s[x]=s[t[x][0]]+s[t[x][1]]+1;}
inline void rotate(int x,int &k){
    int y=f[x],z=f[y],l,r;
    l=t[y][0]==x?0:1,r=l^1;
    if (y==k) k=x;
    else if (t[z][0]==y) t[z][0]=x;
    else t[z][1]=x; 
    f[x]=z,f[y]=x,f[t[x][r]]=y;
    t[y][l]=t[x][r],t[x][r]=y;
    pushup(y);pushup(x);
}
inline void splay(int x,int &k){
    while (x!=k){
        int y=f[x],z=f[y];
        if (y!=k){
            if (t[y][0]==x^t[z][0]==y) rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}

void insert(int k){
    if (!root){
        root=++tot;
        s[tot]=1;
        c[tot]=k;
        return;
    }
    int x=root,xf;
    while (x){
        xf=x;
        ++s[x];
        if (k<c[x]) x=t[x][0];
        else x=t[x][1];
    }
    if (k<c[xf]) t[xf][0]=++tot;
    else t[xf][1]=++tot;
    s[tot]=1;c[tot]=k;f[tot]=xf;
    splay(tot,root);
}
int getrank(int x,int k){
    if (k<=s[t[x][1]]) return getrank(t[x][1],k);
    else if (k==s[t[x][1]]+1) return c[x];
    else return getrank(t[x][0],k-s[t[x][1]]-1);
}
int left(int &x,int xf){
    if (!x) return 0;
    int k;
    if (c[x]+delta<m){
        k=left(t[x][1],x)+s[t[x][0]]+1;
        s[t[x][1]]=s[x]-k;
        x=t[x][1];
        f[x]=xf;
    }
    else{
        k=left(t[x][0],x);
        s[x]-=k;
    }
    return k;
}
int main(){
    scanf("%d%d",&n,&m);
    while (n--){
        char c[5];int k;
        scanf("%s%d",&c,&k);
        if (c[0]=='I'&&k>=m) insert(k-delta);
        if (c[0]=='F') printf("%d\n",k<=s[root]?getrank(root,k)+delta:-1);
        if (c[0]=='A') delta+=k;
        if (c[0]=='S') {delta-=k;result+=left(root,0);}
    }
    printf("%d\n",result);
    return 0;
}