（似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话，是可以跑得飞快的。）
首先看一下题面，发现值域很小，很容易就可以想到用权值线段树维护。
支持：单点加，区间清零，查询第k大的权值线段树。
当然这题有一些细节。
一：如果初始工资低于工资下限，那么这个人就不存在。
二：维护的是第\(k\)大的而非第\(k\)小的。
三：由于是严格小于工资下限，要注意边界的开闭性。最好将公式写出来。
#include<iostream>
#include<cstdio>
using namespace std;
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
//支持：单点加，区间清零，查询第k大的权值线段树。
int tr[2000005],cnt=0;
inline void updt(int X){
tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
if(!tr[X]){
tr[LS]=tr[RS]=0;
}
}
inline void add(int X,int L,int R,int A){
if(L==R){
++tr[X];
return;
}
pshd(X,L,R);
if(A<=MID){
add(LS,L,MID,A);
}else{
add(RS,MID+1,R,A);
}
updt(X);
}
inline void clr(int X,int L,int R,int A,int B){
if(A<=L&&R<=B){
cnt+=tr[X];
tr[X]=0;
return;
}
pshd(X,L,R);
if(A<=MID){
clr(LS,L,MID,A,B);
}
if(B>MID){
clr(RS,MID+1,R,A,B);
}
updt(X);
}
inline int srch(int X,int L,int R,int K){
if(L==R){
return L;
}
pshd(X,L,R);
if(tr[RS]<K){
return srch(LS,L,MID,K-tr[RS]);
}else{
return srch(RS,MID+1,R,K);
}
}
inline int qry(int X,int L,int R,int A,int B){
if(A<=L&&R<=B){
return tr[X];
}
pshd(X,L,R);
int rt=0;
if(A<=MID){
rt+=qry(LS,L,MID,A,B);
}
if(B>MID){
rt+=qry(RS,MID+1,R,A,B);
}
updt(X);
return rt;
}
//1 k 插入大小为k的点
//2 k 全部数加上k
//3 k 全部数减去k
//4 k 查询第k大的值
int n,m,tg=0,k;
char op[4];
void init(){
scanf("%d%d",&n,&m);
--m;
for(int i=1;i<=n;++i){
cin>>op;
scanf("%d",&k);
if(op[0]=='I'){
//注意大于与大等于。
if(k>m){
add(1,1,300001,k+100001+tg);
}
}else if(op[0]=='A'){
tg-=k;
}else if(op[0]=='S'){
tg+=k;
clr(1,1,300001,1,m+100001+tg);
}else if(op[0]=='F'){
if(qry(1,1,300001,1,300001)<k){
puts("-1");
}else{
printf("%d\n",srch(1,1,300001,k)-100001-tg);
}
}
}
printf("%d",cnt);
}
int main(){
init();
return 0;
}