维护全局信息，结点记录该值出现的次数。
支持全局k最小值，可增加删除，查找前驱，后继。相对平衡树，代码简单，快。
当数据较大时，需要离散化。
本题维护一个偏移量，当 A 操作时，不全都加工资 add =x, S 操作 add-=x 。插入时x - add即可，这样仍然是全局偏移量。
输出 add - base就行，base 是防止负数出现
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int base = 200020;
const int maxn = 400020;
struct T{
int l,r,num,lazy;
}t[maxn*4];// t[p] 表示值遇 l 到 r,num是该数出现次数
char s[10];
int minn,add;
void build(int p,int l,int r){
t[p].l = l; t[p].r = r; t[p].num = 0; t[p].lazy = 0;
if(t[p].l==t[p].r) return ;
int mid = (l r)>>1;
build(p*2,l,mid);
build(p*2 1,mid 1,r);
}
void lazy(int p){
if(t[p].lazy==0)return ;
else{
t[p].lazy = 0; //t[p].num = 0;
t[p*2].lazy = 1; t[p*2].num = 0;
t[p*2 1].lazy = 1; t[p*2 1].num = 0;
}
}
void insert(int p,int x){
if(t[p].l==t[p].r){
if(t[p].l==x){
t[p].num ;//插入就是出现次数 ，删除就是--
}
return ;
}
lazy(p);
int mid = (t[p].l t[p].r)>>1;
if(x<=mid)insert(p*2,x);
else insert(p*2 1,x);
t[p].num = t[p*2].num t[p*2 1].num;
}
void update(int p,int x){//工资低于x离开
if(t[p].r<x){
t[p].num = 0; t[p].lazy = 1;
return ;
}
if(t[p].l==t[p].r){
if(t[p].r<x)t[p].num = 0;
return ;
}
lazy(p);
int mid = (t[p].l t[p].r)>>1;
if(x<=mid){
update(p*2,x);
}else{
update(p*2,x);
update(p*2 1,x);
}
t[p].num = t[p*2].num t[p*2 1].num;
}
int ask(int p,int k){//查询全局第 k 小，第 n - k 1 大
//查询n - k 1小则为查询第k大
if(t[p].l==t[p].r)return t[p].l;
lazy(p);
if(k<=t[2*p].num)ask(p*2,k);
else ask(p*2 1,k-t[p*2].num);
}
int main()
{
int kk,x,sum = 0;
scanf("%d%d",&kk,&minn);
build(1,0,400100);
for(int i=0;i<kk;i )
{
scanf("%s%d",s,&x);
if(s[0] == 'I')
{
if(x < minn) continue;
sum ;
insert(1,x-add base);//add为偏移量，不总体操作 加base防负数
}
else if(s[0] == 'A') add = x;
else if(s[0] == 'S')
{
add -= x;
update(1,minn-add base);
}
else{
if(x > t[1].num) printf("-1n");
else printf("%dn",ask(1,t[1].num-x 1) add-base);
}
}
printf("%dn",sum-t[1].num);
return 0;
}
