【洛谷1486】[NOI2004] 郁闷的出纳员（Splay的小运用）

点此看题面

大致题意： 你是一个公司的出纳员，现在有\(n\)个操作，操作有4种：新来一个员工、增加全体员工工资、减少全体员工工资、查询第\(k\)多的工资。若一个员工的工资在某一时刻低于合同上的工资\(m\)，他会立刻离开公司。要你回答每一个询问并统计出离开公司的人数。

平衡树

比较显然，这是一道平衡树的题目。

至于用哪一种平衡树，我感觉这题用\(Splay\)比较方便吧！

这道题目的关键就在于，如何解决增加全体员工工资和减少全体员工工资。

其实，直接用一个变量\(flag\)来存储每个员工的工资变化情况即可。

每当增加全体员工工资，我们直接修改变量的值即可。

但是，如果减少全体员工工资，我们就要考虑是否有员工的工资低于\(m\)，此时就需要工资低于\(m-flag\)的员工从树上删去，那么，我们可以把树上\(m-flag\)的前驱找到，然后将其用\(Splay\)操作旋转直至根节点，将此次要删去的员工数给统计下来后，将根节点更新为根节点的右儿子即可。

还有一个要注意的细节就是，每当新增一个员工时，由于之前每次调整工资时他都不在，所以要先将其工资减去\(flag\)，然后再插入\(Splay\)中。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define LL long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)

#define pc(ch) (pp_<100000?pp[pp_++]=(ch):(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=(ch)))

#define N 100000

int pp_=0;char ff[100000],*A=ff,*B=ff,pp[100000];

using namespace std;

int n,m,rt,tot=0,ans=0,flag=0;

struct splay

{

	int Son[2],Cnt,Size,Val,Father;

}node[N+5];

inline void read(int &x)

{

	x=0;int f=1;char ch;

	while(!isdigit(ch=tc())) f=ch^'-'?1:-1;

	while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

	x*=f;

}

inline void write(int x)

{

	if(x<0) pc('-'),x=-x;

	if(x>9) write(x/10);

	pc(x%10+'0');

}

inline int Which(int x)//判断当前节点是其父亲节点的左儿子还是右儿子

{

	return node[node[x].Father].Son[1]==x;

}

inline void PushUp(int x)//更新当前节点信息

{

	node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+node[x].Cnt;

}

inline void Rotate(int x,int &k)//将当前节点上旋

{

    int fa=node[x].Father,grandpa=node[fa].Father,d=Which(x);

    if(fa^k) node[grandpa].Son[Which(fa)]=x;

    else k=x;

    node[x].Father=grandpa,node[fa].Son[d]=node[x].Son[d^1],node[node[x].Son[d^1]].Father=fa,node[x].Son[d^1]=fa,node[fa].Father=x,PushUp(fa),PushUp(x);

}

inline void Splay(int x,int &k)//将x节点旋转至指定位置k

{

    for(int fa=node[x].Father;x^k;fa=node[x].Father)//只要x还没到目标位置就一直Rotate

    {

        if(fa^k) Rotate(Which(fa)^Which(x)?x:fa,k);

        Rotate(x,k);

    }

}

inline void Insert(int &x,int val,int fa)//插入一个值为val的数

{

	if(!x) {node[x=++tot].Val=val,node[x].Cnt=node[x].Size=1,node[x].Father=fa,node[x].Son[0]=node[x].Son[1]=0,Splay(x,rt);return;}

	if(node[x].Val==val) {++node[x].Cnt,Splay(x,rt);return;}

	if(node[x].Val>val) Insert(node[x].Son[0],val,x);

	else Insert(node[x].Son[1],val,x);

}

inline int get_val(int rk)//求出排名为rk的数的值

{

	int x=rt;

	while(x)

	{

		if(node[node[x].Son[0]].Size>=rk) x=node[x].Son[0];

		else if(node[node[x].Son[0]].Size+node[x].Cnt>=rk) {Splay(x,rt);return node[x].Val;}

		else rk-=node[node[x].Son[0]].Size+node[x].Cnt,x=node[x].Son[1];

	}

}

inline int get_pre(int val)//求出val的前驱的节点编号

{

	int x=rt,pre=0;

	while(x)

	{

		if(node[x].Val<val) pre=x,x=node[x].Son[1];

		else x=node[x].Son[0];

	}

	return pre;

}

inline void Delete(int val)//删除小于val的数

{

	int k=get_pre(val);//k记录val的前驱

	if(k) Splay(k,rt),ans+=node[node[rt].Son[0]].Size+node[rt].Cnt,rt=node[rt].Son[1],PushUp(rt);//将k旋转至根节点，然后更新ans，删除这些节点

}

int main()

{

	register int i;

	for(read(n),read(m),i=1;i<=n;++i)

	{

		char op;int x;while(!isalpha(op=tc()));read(x);

		switch(op)

		{

			case 'I':if(x>=m) Insert(rt,x-flag,0);break;//增加一个新的员工

			case 'A':flag+=x;break;//增加全体员工的工资

			case 'S':Delete(m-(flag-=x));break;//减少全体员工的工资，删去工资少于m的员工

			case 'F':if(node[rt].Size<x) pc('-'),pc('1');else write(get_val(node[rt].Size-x+1)+flag);pc('\n');break;//查询元素，由于询问的是从大到小的排名，所以要求的从小到大的排名就是rt的size减去询问的排名然后再加1

		}

	}

	return write(ans),fwrite(pp,1,pp_,stdout),0;//最后输出答案

}

巴特西

【洛谷1486】[NOI2004] 郁闷的出纳员（Splay的小运用）

平衡树

代码

最新文章

热门文章