题面

题目传送门

思路

看到题目的插入、删除和查询第 k 大操作，就想到了 Treap。

但是全部员工加减工资怎么办？仔细一看，这两种操作总条数不会超过 100，所以遍历整棵树更改数值就好了。

在增加工资的时候，一定不会有人离开。

在减少工资的时候，我们不断找工资底线 k 的前驱，如果它存在，就删除它。

最后的离开人数就是插入操作的次数减去最后的人数。

代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,y,l,r,size,cnt;
};
node s[1000001];
long long n,q,top=0,cnt=0,len=0,k;
long long root=0;
void dfs(long long x,int k){
	if (!x){
		return;
	}
	s[x].x+=k;
	dfs(s[x].l,k);
	dfs(s[x].r,k);
}
void update(long long x){
	s[x].size=s[s[x].l].size+s[s[x].r].size+s[x].cnt;
}
void rotr(long long &x){
	long long l=s[x].l;
	s[x].l=s[l].r;
	s[l].r=x;
	s[l].size=s[x].size;
	update(x);
	x=l;
}
void rotl(long long &x){
	long long r=s[x].r;
	s[x].r=s[r].l;
	s[r].l=x;
	s[r].size=s[x].size;
	update(x);
	x=r;
}
void add(long long &x,long long data){
	if (!x){
		x=++top;
		s[x].x=data;
		s[x].y=rand()%19260817;
		s[x].cnt=1;
		s[x].size=1;
		s[x].l=0;
		s[x].r=0;
		return;
	}
	s[x].size++;
	if (s[x].x==data){
		s[x].cnt++;
	}else if (data<s[x].x){
		add(s[x].l,data);
		if (s[x].y>s[s[x].l].y){
			rotr(x);
		}
	}else{
		add(s[x].r,data);
		if (s[x].y>s[s[x].r].y){
			rotl(x);
		}
	}
}
void del(long long &x,long long data){
	if (s[x].x==data){
		if (s[x].cnt>1){
			s[x].cnt--;
			s[x].size--;
			return;
		}
		if (!s[x].l||!s[x].r){
			x=s[x].l+s[x].r;
			return;
		}
		if (s[s[x].l].y<s[s[x].r].y){
			rotr(x);
			del(x,data);
		}else{
			rotl(x);
			del(x,data);
		}
		return;
	}
	s[x].size--;
	if (data<s[x].x){
		del(s[x].l,data);
	}else{
		del(s[x].r,data);
	}
}
long long pre(long long data){
	long long now=root,res=-2147483647;
	while (now){
		if (s[now].x<data){
			res=s[now].x;
			now=s[now].r;
		}else{
			now=s[now].l;
		}
	}
	return res;
}
long long nxt(long long data){
	long long now=root,res=2147483647;
	while (now){
		if (s[now].x>data){
			res=s[now].x;
			now=s[now].l;
		}else{
			now=s[now].r;
		}
	}
	return res;
}
long long querykth(long long k){
	long long now=root;
	while (now){
		if (s[s[now].l].size<k&&s[s[now].l].size+s[now].cnt>=k){
			return s[now].x;
		}
		if (s[s[now].l].size>=k){
			now=s[now].l;
		}else{
			k-=s[s[now].l].size+s[now].cnt;
			now=s[now].r;
		}
	}
	return 0;
}
long long queryrank(long long data){
	long long now=root,res=0;
	while (now){
		if (data==s[now].x){
			return res+s[s[now].l].size+1;
		}
		if (data<s[now].x){
			now=s[now].l;
		}else{
			res+=s[s[now].l].size+s[now].cnt;
			now=s[now].r;
		}
	}
	return res;
}
void check(){
	int x=pre(k);
	while (x<k&&x!=-2147483647){
		del(root,x);
		len--;
		x=pre(k);
	}
}
int main(){
	srand(time(0));
	cin>>q>>k;
	string t;
	long long x;
	while (q--){
		cin>>t>>x;
		if (t=="I"){
			if (x<k){
				continue;
			}
			len++;
			cnt++;
			add(root,x);
		}
		if (t=="A"){
			dfs(root,x);
		}
		if (t=="S"){
			dfs(root,-x);
			check();
		}
		if (t=="F"){
			if (x>len){
				cout<<"-1"<<endl;
				continue;
			}
			cout<<querykth(len-x+1)<<endl;
		}
	}
	cout<<cnt-len;
}