题意

维护一个平衡树,4种操作

• I命令 添加新的值

• A命令 将平衡树的所有值加上k

• S命令 将平衡树的所有值减上k

• F命令 输出排名第k大的值

同时把平衡树中小于工资下界的值删除,并记录

最后输出删除了多少个值(不含值低于工资下界的)

思路

实际上,我们需要在平衡树中添加两个新的操作

• 统计有多少个值小于工资下界,同时删除小于工资下界的值

int pop_range()
{
	split(工资下界-1,根,左边,右边);
	根=右边;
	返回 左边的子树大小;
}

• 区间"加减"操作,原理就是懒标记,就像线段树一样

void pushdown(int 结点)
{
	如果(懒标记为空 或 结点为空)返回;
	左边的懒标记+=结点的懒标记;
	右边的懒标记+=结点的懒标记;
	结点的值+=结点的懒标记;
	结点的懒标记=0;
}

代码

#include<bits/stdc++.h>
using namespace std;
template<typename Type,int Size>
class FHQTreap
{
	protected:
		struct node
		{
			Type data;
			int size,r,ls,rs;
			int lazy;
		};
		node v[Size];
		int root=0,tot=0;
		int new_p(Type x)
		{
			v[++tot]={x,1,rand(),0,0};
			return tot;
		}
		void pushup(int index)
		{
			v[index].size=1+v[v[index].ls].size+v[v[index].rs].size;
		}
		void pushdown(int index)
		{
			if(!v[index].lazy || !index)return;
			v[v[index].ls].lazy+=v[index].lazy;
			v[v[index].rs].lazy+=v[index].lazy;
			v[index].data+=v[index].lazy;
			v[index].lazy=0;
		}
		void split(Type x,int index,int &ls,int &rs)
		{
			if(!index){ls=rs=0;return;}
			pushdown(index);
			if(v[index].data<=x)
				ls=index,split(x,v[index].rs,v[index].rs,rs);
			else
				rs=index,split(x,v[index].ls,ls,v[index].ls);
			pushup(index);
		}
		int merge(int ls,int rs)
		{
			if(!ls || !rs)return ls+rs;
			if(v[ls].r>v[rs].r)
			{
				pushdown(ls);
				v[ls].rs=merge(v[ls].rs,rs);
				pushup(ls);
				return ls;
			}
			else
			{
				pushdown(rs);
				v[rs].ls=merge(ls,v[rs].ls);
				pushup(rs);
				return rs;
			}
		}
		Type get_topk(int x,int index)
		{
			pushdown(index);
			int lss=v[v[index].ls].size;
			if(x==lss+1)return v[index].data;
			if(x<lss+1) return get_topk(x,v[index].ls);
			else  return get_topk(x-lss-1,v[index].rs);
		}
	public:
		int size()
		{
			return v[root].size;
		}
		void push(Type x)
		{
			int ls,rs;
			split(x,root,ls,rs);
			root=merge(merge(ls,new_p(x)),rs);
		}
		Type get_topk(int x)
		{
			return get_topk(x,root);
		}
		int pop_range(int x)
		{
			int ls,rs;
			split(x-1,root,ls,rs);
			root=rs;
			return v[ls].size;
		}
		void add(int k)
		{
			v[root].lazy+=k;
			pushdown(root);
		}
};
FHQTreap<int,1000010>a;
int n,mi,ans=0;
int main()
{
	cin>>n>>mi;
	while(n--)
	{
		char o;int k;cin>>o>>k;
		if(o=='I')
		{
			if(k>=mi)a.push(k);
		}
		else if(o=='A')a.add(k);
		else if(o=='S')a.add(-k);
		else if(o=='F')
		{
			if(a.size()>=k)cout<<a.get_topk(a.size()-k+1)<<"\n";
			else cout<<"-1\n";
		}
		ans+=a.pop_range(mi);
	}
	cout<<ans;
	return 0;
}

彩蛋

暴力也能过