[BZOJ1503]郁闷的出纳员（Splay）

Description

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。

老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

PS：最后还要求出踢出员工的数量

Solution

首先这题要求数列第K大的数，涉及到插入、删除和修改，

修改是对于整个数列，显然不能一个一个改，记录一个类似lazy_tag的标记即可

插入的时候将Num减去tag再插入

全体增加直接累加tag就行，但全体减少的话可能会踢人，进行删除操作判断

在删除的时候统计删除节点数目

Tips：插入对于s(u)的维护，需要考虑到父节点们，被坑了好久

Code

#include <cstdio>

#include <algorithm>

#define N 100010

#define lc(x) T[(x)][0]

using namespace std;

int n,m,rt,tot,T[N][2],k[N],fa[N],s[N],tag,num;

void rotate(int p){

	int q=fa[p],y=fa[q],x=(T[q][1]==p);

	T[q][x]=T[p][x^1],fa[T[q][x]]=q;

	T[p][x^1]=q,fa[q]=p;

	fa[p]=y;

	if(y){

		if(T[y][0]==q) T[y][0]=p;

		else if(T[y][1]==q) T[y][1]=p;

	}

	s[p]=s[q];

	s[q]=s[T[q][0]]+s[T[q][1]]+1;

}

void splay(int x){

	for(int y;y=fa[x];rotate(x))

		if(fa[y]) rotate((x==lc(y))==(y==lc(fa[y]))?y:x);

	rt=x;

}

void Insert(int v){

	if(!rt){

		rt=++tot;

		T[rt][0]=T[rt][1]=0;

		k[rt]=v;

		fa[rt]=0;

		s[rt]=1;

		return;

	}

	int x=rt,y;

	while(1){

		s[x]++;

		y=T[x][k[x]<v];

		if(!y){

			y=++tot;

			k[y]=v;

			fa[y]=x;

			s[y]=1;

			T[y][0]=T[y][1]=0;

			T[x][k[x]<v]=y;

			break;

		}

		x=y;

	}

	splay(y);

}

void Del(int x){

	splay(x);

	num+=s[T[x][0]]+1;

	rt=T[x][1];

	fa[rt]=0;

}

void DEL(){

	int x=rt;

	while(x){

		int u=0;

		if(k[x]+tag>=m) x=T[x][0];

		else u=x,x=T[x][1];

		if(u) Del(u);

	}

}

int Find(int x){

	int r=0;

	for(int u=rt;;){

		if(s[T[u][1]]+r+1==x) return k[u];

		if(s[T[u][1]]+r+1<x) r+=s[T[u][1]]+1,u=T[u][0];

		else u=T[u][1];

	}

}

int main(){

	scanf("%d%d",&n,&m);

	while(n--){

		char ch=getchar();int t;

		while(ch!='I'&&ch!='A'&&ch!='S'&&ch!='F') ch=getchar();

		scanf("%d",&t);

		if(ch=='I'&&t>=m) Insert(t-tag);

		else if(ch=='A') tag+=t;

		else if(ch=='S') {tag-=t;DEL();}

		else if(ch=='F'){

			if(t>s[rt]) printf("-1\n");

			else printf("%d\n",Find(t)+tag);

		}

	}

	printf("%d\n",num);

	return 0;

}

巴特西

[BZOJ1503]郁闷的出纳员（Splay）

Description

PS：最后还要求出踢出员工的数量

Solution

Code

最新文章

热门文章