练习模板
//插入，删除（一棵子树），找第k大
//递归 6556 kb 1076 ms
//非递归6552 kb 1064 ms
#include<cstdio>
const int inf = ~0u>>2;///可能是右移1位的话+1就变负 而不是仍为INF,所以不太好,于是移两位
#define KT (ch[ ch[rt][1] ][0])///根节点的右儿子的左儿子,经常要被操作的那一个
const int maxn = 200010;
int lim;
struct SplayTree {
int sz[maxn];///根节点和子树的大小之和
int ch[maxn][2];
int pre[maxn];
int rt,top;
inline void up(int x){
sz[x] = cnt[x] + sz[ ch[x][0] ] + sz[ ch[x][1] ];
}
inline void Rotate(int x,int f){
int y=pre[x];
ch[y][!f] = ch[x][f];
pre[ ch[x][f] ] = y;
pre[x] = pre[y];
if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] =x;
ch[x][f] = y;
pre[y] = x;
up(y);
}
inline void Splay(int x,int goal){//将x旋转到goal的下面
while(pre[x] != goal){
if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][0] == x);
else {
int y=pre[x],z=pre[y];
int f = (ch[z][0]==y);
if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f);
else Rotate(y,f),Rotate(x,f);
}
//puts("here");
}
up(x);
if(goal==0) rt=x;
}
inline int RTO(int k,int goal){//将第k位数旋转到goal的下面
int x=rt;///非递归的方式实现
while(sz[ ch[x][0] ] >= k ||k >sz[ ch[x][0] ] + cnt[x] ) {
if(k <= sz[ ch[x][0] ]) x=ch[x][0];
else {
k-=(sz[ ch[x][0] ]+cnt[x]);
x = ch[x][1];
}
}
Splay(x,goal);
return val[x];
}
inline void vist(int x){
if(x){
printf("结点%2d : 左儿子 %2d 右儿子 %2d %2d sz=%d\n",x,ch[x][0],ch[x][1],val[x],sz[x]);
vist(ch[x][0]);
vist(ch[x][1]);
}
}
inline void Newnode(int &x,int c){///添加一个裸的节点,第一个参数指向它
x=++top;///top指数组中的最大值
ch[x][0] = ch[x][1] = pre[x] = 0;
sz[x]=1; cnt[x]=1;
val[x] = c;
}
inline void init(){
sum = ch[0][0] = ch[0][1] = pre[0] = sz[0] = 0;
rt = top = 0;
cnt[0] = 0;
}
inline void Insert(int &x,int key,int f){
if(!x) {///如果x是空指针,就是末端接上一个节点
Newnode(x,key);
pre[x]=f;///把新节点接在尾部即可
Splay(x,0);///旋转到根
return ;
}
if(key==val[x]){///插入的员工有可能和之前的工资一样
cnt[x]++;
sz[x]++;
Splay(x,0);///不用新加节点,但是要旋转到根
return ;
}
else if(key<val[x]) {
Insert(ch[x][0],key,x);
}
else {
Insert(ch[x][1],key,x);
}///不是等于的话就用递归找,直到找到末端或者相等
up(x);
}
void del(int &x,int f){///从头开始搜
if(!x) return ;///空 退出
if(val[x]>=lim){///如果当前节点不需要删,找左儿子
del(ch[x][0],x);
} else {///当前节点需要删
sum+=sz[ch[x][0]]+cnt[x];
x=ch[x][1];
pre[x]=f;
if(f==0) rt=x;///删掉当前节点及其左儿子,将右儿子和自己的父节点相连
del(x,f);///继续删右儿子
}
if(x) up(x);///更新左右儿子到自己,这题没有标记,因为不是区间更新
}
inline void update(){///更新就是看看有没有人可删
del(rt,0);
}
inline int find_kth(int x,int k){
if(k<=sz[ch[x][0]]) {///在左儿子内
return find_kth(ch[x][0],k);///以左儿子为根
}else if(k > sz[ ch[x][0] ] + cnt[x] )///在右儿子内
return find_kth(ch[x][1],k-sz[ch[x][0]]-cnt[x]);///右
else{
Splay(x,0);///在当前节点内,旋转到根
return val[x];///返回当前节点值,即工资
}
}
int cnt[maxn];///当前节点的人数(工资相同)
int val[maxn];//工资
int sum;///离开公司的员工总数
}spt;
int main(){
int n;
char op[5];
scanf("%d%d",&n,&lim);
int lim0=lim;
spt.init();
while(n--){
int k;
scanf("%s%d",op,&k);
if(op[0]=='I'){
if(k<lim0) continue;
spt.Insert(spt.rt,k+lim-lim0,0);///输入的是实际工资,需要换算成相对工资之后插入
}
else if(op[0]=='A'){///好吧,lim代替了工资的加减...用lim0表示实际lim,lim则用来删人
lim-=k;
}
else if(op[0]=='S'){
lim+=k;
if(spt.sz[spt.rt]>0) spt.update();///如果公司不空,就更新
}
else {///询问
int sz=spt.sz[spt.rt];
if(k>sz) printf("-1\n");
else {
//printf("%d\n",spt.find_kth(spt.rt,sz-k+1)-lim+lim0);///问第k多的,函数是第k少的,调节一下
printf("%d\n",spt.RTO(sz-k+1,0)-lim+lim0);
}
}
// spt.vist(spt.rt);
}
printf("%d\n",spt.sum);
return 0;
}