洛谷P1486 [NOI2004] 郁闷的出纳员题解

题目链接：P1486 [NOI2004] 郁闷的出纳员

题意：维护一个数据结构，支持

插入一个大小为 $k$ 的值，小于下界时不插入

所有元素加上 $k$

所有元素减去 $k$ ，小于下界的删除

查询所有元素中的 $k$ 大值

最后输出删除的元素个数（两元素相等算两个）

可以用平衡树来解决本题

听说正解是splay，不过我来讲一种替罪羊树的写法

我们可以维护一个 $d$ ，表示每次加减的变化

这样每个元素就可以用 $x+d$ 的形式表示了

在平衡树里放原来的数减去插入时的 $d$ ，即 $k-d$

这样输出的时候就是正常的数了

那小于下界的怎么搞呢？

根据替罪羊树的性质，我们可以直接把整课树重构

在Flatten操作时判断当前元素 $x$ 加上 $d$ 是否超过下界，且存在，否则就直接不管它了

$k$ 大值直接查 $num1-k+1$ 小值就好了

这个 $num1$ 表示每次操作后的剩余结点数（两元素相等算两个）

因为它最后还有个询问删除的，再记录一下总插入结点数（两元素相等算两个） $num2$ ，答案就是 $num2-num1$

这样整个算法的时间复杂度为 $O(n\log n)$

本题在luogu上的数据是windows下造的，所以还要注意换行符是\r\n，不是linux下的\n

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN (int)(3e5+5)
#define gc() getchar()
#define pc(a) putchar(a)
template<typename T>inline void read(T &k)
{
	char ch=gc();T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
	k=x*f;
}
template<typename T>inline void write(T k)
{
	if(k<0){k=-k;pc('-');}
	if(k>9)write(k/10);
	pc(k%10+'0');
}
namespace BT
{
	#define ls(at) a[at].l
	#define rs(at) a[at].r
	int n,m;
	int d,num1,num2;
	struct node
	{
		int l,r,num,cnt,s,sz,sd;
	}a[MAXN];
	double alpha=0.75;
	int tot,rt;
	int tmp[MAXN];
	int New(int x)
	{
		a[++tot]={0,0,x,1,1,1,1};
		return tot;
	}
	void push_up(int at)
	{
		a[at].s=a[ls(at)].s+a[rs(at)].s+1;
		a[at].sz=a[ls(at)].sz+a[rs(at)].sz+a[at].cnt;
		a[at].sd=a[ls(at)].sd+a[rs(at)].sd+(a[at].cnt!=0);
	}
	bool CanR(int at)
	{
		double x=a[at].s*alpha;
		return a[at].cnt&&(x<=(double)max(a[ls(at)].s,a[rs(at)].s)||(double)a[at].sd<=x);
	}
	void CanR_flatten(int &idx,int at)
	{
		if(!at)return;
		CanR_flatten(idx,ls(at));
		if(a[at].cnt)
		{
			if(a[at].num+d>=m)
				tmp[++idx]=at; //在这里就筛掉不满足下界的
			else num1-=a[at].cnt; // 注意不是减1，因为可能有相同的元素
		}
		CanR_flatten(idx,rs(at));
	}
	int CanR_build(int l,int r)
	{
		if(l>=r)return 0;
		int mid=(l+r)>>1;
		int &at=tmp[mid];
		ls(at)=CanR_build(l,mid);
		rs(at)=CanR_build(mid+1,r);
		push_up(at);
		return at;
	}
	void rebuild(int &at)
	{
		int idx=0;
		CanR_flatten(idx,at);
		at=CanR_build(1,idx+1);
	}
	void insert(int x,int &at)
	{
		if(!at){at=New(x);return;}
		if(a[at].num==x)++a[at].cnt;
		else if(x<a[at].num)insert(x,ls(at));
		else insert(x,rs(at));
		push_up(at);
		if(CanR(at))rebuild(at);
	}
	void remove(int x,int &at)
	{
		if(!at)return;
		if(x==a[at].num)
		{
			if(a[at].cnt)
				--a[at].cnt;
		}else if(x<a[at].num)remove(x,ls(at));
		else remove(x,rs(at));
		push_up(at);
		if(CanR(at))rebuild(at);
	}
	int uprbd(int x,int at)
	{
		if(!at)return 1;
		if(x==a[at].num&&a[at].cnt)return a[ls(at)].sz+a[at].cnt+1;
		else if(x<a[at].num)return uprbd(x,ls(at));
		else return uprbd(x,rs(at))+a[ls(at)].sz+a[at].cnt;
	}
	int uprbd_gt(int x,int at)
	{
		if(!at)return 0;
		if(x==a[at].num&&a[at].cnt)return a[ls(at)].sz;
		else if(x<a[at].num)return uprbd_gt(x,ls(at));
		else return uprbd_gt(x,rs(at))+a[ls(at)].sz+a[at].cnt;
	}
	int getval(int x,int at)
	{
		if(!at)return INF;
		if(x<=a[ls(at)].sz)return getval(x,ls(at));
		if(x<=a[ls(at)].sz+a[at].cnt)return a[at].num;
		else return getval(x-a[ls(at)].sz-a[at].cnt,rs(at));
	}
	int getpre(int x,int at){return getval(uprbd_gt(x,at),at);}
	int getnext(int x,int at){return getval(uprbd(x,at),at);}
	int getrank(int x,int at){return uprbd_gt(x,at)+1;}
}
signed main()
{
	using namespace BT; // 替罪羊树 qwq
	read(n);read(m);
	for(int i=1; i<=n; i++)
	{
		char op;int x;char t;
		//gc(); //win下要用
		op=gc();read(x);
		if(op=='I'&&x>=m) // 不满下界的直接不管了
		{
			insert(x-d,rt);
			++num1;++num2;
		}
		if(op=='A')d+=x;
		if(op=='F')
		{
			if(num1<x)puts("-1"); // 不满k个数
			else 
			{
				write(getval(num1-x+1,rt)+d);
				pc('\n');
			}
		}
		if(op=='S')
		{
			d-=x;
			rebuild(rt); // 直接重构
		}
	}
	write(num2-num1);pc('\n');
	return 0;
}