题目大意：维护一个平衡树，支持插入一个数，删除小于一个值的所有数，K 大值查询，每个节点权值加减一个数。
题解：所有节点权值加减操作可以考虑直接维护一个全局标记，删除小于一个值的所有数字为一个二分的过程，复杂度为 \(O(logn)\)，具体做法为：若当前子树根节点权值小于 X，则直接删除整颗左子树，继续遍历，否则访问左子树。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
int n,mi,tag,ans;
struct node{
#define ls(x) t[x].lc
#define rs(x) t[x].rc
int lc,rc,val,rd,size,cnt;
}t[maxn];
int tot,root;
inline int newnode(int val){
++tot,t[tot].val=val,t[tot].rd=rand(),t[tot].size=t[tot].cnt=1;
return tot;
}
inline void pushup(int o){
t[o].size=t[ls(o)].size+t[rs(o)].size+t[o].cnt;
}
inline void zig(int &o){
int lson=ls(o);
ls(o)=rs(lson),rs(lson)=o,o=lson;
pushup(rs(o)),pushup(o);
}
inline void zag(int &o){
int rson=rs(o);
rs(o)=ls(rson),ls(rson)=o,o=rson;
pushup(ls(o)),pushup(o);
}
void insert(int &o,int val){
if(!o)o=newnode(val);
else if(t[o].val==val)++t[o].cnt,++t[o].size;
else if(val<t[o].val){
++t[o].size,insert(ls(o),val);
if(t[ls(o)].rd>t[o].rd)zig(o);
}else{
++t[o].size,insert(rs(o),val);
if(t[rs(o)].rd>t[o].rd)zag(o);
}
}
void remove(int &o,int val){
if(!o)return;
else if(t[o].val>=val)remove(ls(o),val);
else{
ans+=t[o].cnt+t[ls(o)].size;
o=rs(o),remove(o,val);
}
pushup(o);
}
int kth(int o,int k){
if(k<=t[ls(o)].size)return kth(ls(o),k);
else if(k>t[ls(o)].size+t[o].cnt)return kth(rs(o),k-t[ls(o)].size-t[o].cnt);
else return t[o].val;
}
void solve(){
char opt[3];int val;
scanf("%d%d",&n,&mi);
while(n--){
scanf("%s%d",opt,&val);
if(opt[0]=='I'){
if(val<mi)continue;
insert(root,val-tag);
}else if(opt[0]=='A')tag+=val;
else if(opt[0]=='S'){
tag-=val;
remove(root,mi-tag);
}else{
if(val>t[root].size)puts("-1");
else printf("%d\n",kth(root,t[root].size-val+1)+tag);
}
}
printf("%d\n",ans);
}
int main(){
solve();
return 0;
}