[NOI2004]郁闷的出纳员

题目描述

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

输入格式

第一行有两个非负整数n和min。n表示下面有多少条命令,min表示工资下界。接下来的n行,每行表示一条命令。
命令可以是以下四种之一:
1. I命令 I_k 新建一个工资档案,初始工资为k。
如果某员工的初始工资低于工资下界,他将立刻离开公司。
2. A命令 A_k 把每位员工的工资加上k
3. S命令 S_k 把每位员工的工资扣除k
4. F命令 Fk 查询第k多的工资

表示一个空格,I命令、A命令、S命令中的k是一个非负整数,F命令中的k是一个正整数。在初始时,可以认为公司里一个员工也没有。
I命令的条数不超过100000
A命令和S命令的总条数不超过100
F命令的条数不超过100000
每次工资调整的调整量不超过1000
新员工的工资不超过100000

输出格式

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

分析:

这道题是一道非常简单粗暴的平衡树,我们在计算加减工资的时候只要维护一个值,然后接下来加入的人的初始工资都减去这个值,然后减工资的时候只要把工资低于minn-add-1 的都去掉就好了….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define db double
#define fi first
#define se second
const LL N=1e5+10;
const LL inf=0x3f3f3f3f;
const LL mod=12345678;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
namespace Treap
{
    int cnt,root;
    struct Node {int key,siz,p,ch[2];}node[N];
    Node new_node(int key)
    {
        node[++cnt].key=key;
        node[cnt].p=rand();
        node[cnt].siz=1;
    }
    void updata(int now)
    {
        int l=node[now].ch[0],r=node[now].ch[1];
        node[now].siz=node[l].siz+node[r].siz+1;
    }
    int merge(int x,int y)
    {
        if(node[x].siz==0) return y;
        if(node[y].siz==0) return x;
        if(node[x].p<node[y].p)
        {
            node[x].ch[1]=merge(node[x].ch[1],y);
            updata(x);return x;
        }
        else
        {
            node[y].ch[0]=merge(x,node[y].ch[0]);
            updata(y);return y;
        }
    }
    void split_k(int now,int &x,int &y,int k)
    {
        if(node[now].siz==0) {x=y=0;return;}
        if(node[node[now].ch[0]].siz+1<=k) x=now,split_k(node[now].ch[1],node[now].ch[1],y,k-node[node[now].ch[0]].siz-1);
        else y=now,split_k(node[now].ch[0],x,node[now].ch[0],k);
        updata(now);
    }
    void split_key(int now,int &x,int &y,int k)
    {
        if(node[now].siz==0) {x=y=0;return;}
        if(node[now].key<=k) x=now,split_key(node[now].ch[1],node[now].ch[1],y,k);
        else y=now,split_key(node[now].ch[0],x,node[now].ch[0],k);
        updata(now);
    }
}
using namespace Treap;
int n,minn,add,ans;
signed main()
{
    read(n),read(minn);root=0;
    for(int cas=1;cas<=n;cas++)
    {
        char s[100];int k,a,b,c,d;scanf("%s%d",s+1,&k);
        if(s[1]=='I') 
        {
            if(k<minn) continue;ans++;
            split_key(root,a,b,k-add);new_node(k-add);
            a=merge(a,cnt);
            root=merge(a,b);
        }
        else if(s[1]=='A') add+=k;
        else if(s[1]=='S')
        {
            add-=k;
            split_key(root,a,b,minn-add-1);
            root=b;
        }
        else 
        {
            k=node[root].siz-k+1;
            if(k<=0){puts("-1");continue;}
            split_k(root,a,b,k);
            split_k(a,c,d,k-1);
            printf("%d\n",node[d].key+add);
            a=merge(c,d);
            root=merge(a,b);
        }
    }
    printf("%d\n",ans-node[root].siz);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注