12
4
2015
0

【NOI2008】【Treap】【SBT】郁闷的出纳员

 

1482 -- 【NOI2004】郁闷的出纳员

 

Description

  OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
  工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。
  老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。
  好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?

 

Input

  第一行有两个非负整数n和min。n表示下面有多少条命令,min表示工资下界。 
  接下来的n行,每行表示一条命令。命令可以是以下四种之一: 
    
  _(下划线)表示一个空格,I命令、A命令、S命令中的k是一个非负整数,F命令中的k是一个正整数。 
  在初始时,可以认为公司里一个员工也没有 

 

Output

  输出文件的行数为F命令的条数加一。
  对于每条F命令,你的程序要输出一行,仅包含一个整数,为当前工资第k多的员工所拿的工资数,如果k大于目前员工的数目,则输出-1。
  输出文件的最后一行包含一个整数,为离开公司的员工的总数。

 

Sample Input

  9 10   I 60   I 70   S 50   F 2   I 30   S 15   A 5   F 1   F 2

 

Sample Output

  10   20   -1   2

 

Hint

  I命令的条数不超过100000
  A命令和S命令的总条数不超过100
  F命令的条数不超过100000
  每次工资调整的调整量不超过1000
  新员工的工资不超过100000

把一个变量用作类似线段树中的延迟标记,不需要在每次加或者减的时候进行全部更新。在后来插入的结点中,应该当之前的延迟算进去,如果初始就小于下限的不添加,而且也不算作最后离开的人数。

在删除的时候,如果根结点小于下限,说明左子树以及根结点都小于下限,直接把右子树作为根。对新的树进行处理。

如果根结点大于下限,说明右子树也全部大于下限,对左子树进行处理,最后更新根的size。(FROM cxlove)


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
const int M=100000+5;
struct data{
	int l,r,num,pro,s;
}t[M];
int n,minn;
int rt,tot,cnt,delta;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
void update(int p)
{
	t[p].s=t[t[p].l].s+t[t[p].r].s+1;
}
void Zig(int &p)
{
	int k=t[p].r;
	t[p].r=t[k].l;
	t[k].l=p;
	t[k].s=t[p].s;//整棵子树的大小没有改变,只是根节点变换
	update(p);
	p=k;//根节点改为k
}
void Zag(int &p)
{
	int k=t[p].l;
	t[p].l=t[k].r;
	t[k].r=p;
	t[k].s=t[p].s;
	update(p);
	p=k;
}
void Insert(int &p,int x)
{
	if(p==0)
	{
		tot++;p=tot;
		t[p].pro=rand();
		t[p].num=x;
		t[p].s=1;
		return;
	}
	t[p].s++;
	if(x<t[p].num)
	{
		Insert(t[p].l,x);
		if(t[t[p].l].pro<t[p].pro) Zag(p);
	}
	else
	{
		Insert(t[p].r,x);
		if(t[t[p].r].pro<t[p].pro) Zig(p);
	}
}
int Del(int &p,int x)
{
	int k;//记录上层递归删除节点数
	if(!p) return 0;
	if(x<=t[p].num)//一定要加=
	{
		k=Del(t[p].l,x);
		t[p].s-=k;
		return k;
	}
	else
	{
		k=t[t[p].l].s+1;
		p=t[p].r;
		return k+Del(p,x);
	}
}
int Findk(int p,int k)
{
	if(t[t[p].l].s+1==k) return t[p].num+delta;
	else if(t[t[p].l].s+1<k) return Findk(t[p].r,k-t[t[p].l].s-1);//减去的1是根节点
	else return Findk(t[p].l,k);
}
int main()
{
	char ch[1];
	int x;
	rt=0;tot=0;cnt=0;
//	srand(1);
	n=read();minn=read();
	while(n--)
	{
		scanf("%s%d",ch,&x);//不要加&
		if(ch[0]=='I') if(x>=minn) Insert(rt,x-delta);
		if(ch[0]=='A') delta+=x;
		if(ch[0]=='S')
		{
			delta-=x;
			cnt+=Del(rt,minn-delta);
		}
		if(ch[0]=='F')
		{
			if(x>t[rt].s) puts("-1");
			else printf("%d\n",Findk(rt,t[rt].s-x+1));
		}
	}
	printf("%d\n",cnt);
	return 0;
}

treap模板已写熟,向SBT迈进

各种写法提交了n次..%%%Gvv

 

1482 sdfzgww Accepted 100 466 ms 4243 KB 2.24 KB G++(0x)  2015-11-16 23:45:57
564586 1482 sdfzgww Accepted 100 484 ms 6977 KB 2.24 KB G++(0x)  2015-11-16 23:44:47
564581 1482 sdfzgww Accepted 100 495 ms 28852 KB 2.09 KB G++(0x)  2015-11-16 23:11:42
567659 1482 sdfz_ZWR Accepted 100 505 ms 16521 KB 3.77 KB G++  2015-12-04 22:58:46
567502 1482 sdfz_ZWR Accepted 100 521 ms 3067 KB 2.85 KB G++  2015-12-04 17:59:40
512770 1482 liuyunhui123 Accepted 100 533 ms 3239 KB 2.76 KB G++  2015-05-26 16:24:59
567660 1482 sdfz_ZWR Accepted 100 535 ms 3068 KB 2.09 KB G++  2015-12-04 23:21:18
567475 1482 SDFZ_YSM Accepted 100 577 ms 5995 KB 1.81 KB G++  2015-12-04 16:59:36
348989 1482 cqtest Accepted 100 580 ms 6038 KB 3.36 KB G++(0x)  2012-12-01 08:33:28
459755 1482 sxrjl Accepted 100 591 ms 20881 KB 2.32 KB G++  2014-09-06 16:39:03
567429 1482 sdfz_ZWR Accepted 100 596 ms 3461 KB 1.8 KB G++  2015-12-03 15:31:51

 

Category: 伸展树 | Tags: | Read Count: 370

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com