权值线段树。
我们只用维护一个人是否存在，以及他当前排名，而不关心工资的具体值，这个可以直接算。
不难发现，如果不考虑新的员工，所有员工的工资的差值是不变的。
而加进来一个新的员工时，其工资为\(x\)，假设当前工资变化量为\(delta\)，那么这个新员工与原来员工工资\(x_i\)的工资差就是\(x-x_i-delta\)。
根据这点，我们不难想到对所有员工仅维护\(x_i-delta\)这个东西，询问时加上当前的\(delta\)即可。
即维护一颗权值线段树，维护\(x_i-delta\)出现的次数，并实时整体二分求第k大即可。
注意一些小细节，\(x_i-delta\)有可能为负数，因此我们将维护的值域整体向右平移\(N\)。
话说这个题不加lazytag也能轻松跑过，数据真的弱。
参考代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 401000
#define M 200010
#define MOD 2520
#define E 1e-12
using namespace std;
inline int read()
{
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct tree{
int l,r;
int sum,rem;
}t[N<<2];
int n,lim,delta,now,go;
inline void pushdown(int p)
{
if(t[p].rem){
t[p<<1].sum=t[p<<1|1].sum=0;
t[p<<1].rem=t[p<<1|1].rem=1;
t[p].rem=0;
}
}
inline void pushup(int p){t[p].sum=t[p<<1].sum+t[p<<1|1].sum;}
inline void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r){t[p].sum=0;return;}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
inline void change(int p,int x,int val)
{
if(t[p].l==t[p].r){
t[p].sum+=val;return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) change(p<<1,x,val);
else change(p<<1|1,x,val);
pushup(p);
}
inline int query(int p,int k)
{
if(t[p].l==t[p].r) return t[p].l;
pushdown(p);
if(t[p<<1].sum>=k) return query(p<<1,k);
else return query(p<<1|1,k-t[p<<1].sum);
}
inline void upd(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r){
if(t[p].sum) now-=t[p].sum,go+=t[p].sum;
t[p].sum=0,t[p].rem=1;return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) upd(p<<1,l,r);
if(r>mid) upd(p<<1|1,l,r);
pushup(p);
}
int main()
{
n=read(),lim=read();
char op[2];
build(1,1,N);
for(int i=1;i<=n;++i){
scanf("%s",op);
int k=read();
if(op[0]=='I'){
if(k>=lim) change(1,k-delta+M,1),now++;
}
else if(op[0]=='A') delta+=k;
else if(op[0]=='S') delta-=k,upd(1,1,lim-delta-1+M);
else if(op[0]=='F'){
if(k>now) puts("-1");
else printf("%d\n",query(1,now-k+1)+delta-M);
}
}
cout<<go<<endl;
return 0;
}