洛谷P1486 [NOI2004]郁悶的出納員(splay)

題目描述

OIER公司是一家大型專業化軟體公司，有着數以萬計的員工。作為一名出納員，我的任務之一便是統計每位員工的工資。這本來是一份不錯的工作，但是令人郁悶的是，我們的老闆反複無常，經常調整員工的工資。如果他心情好，就可能把每位員工的工資加上一個相同的量。反之，如果心情不好，就可能把他們的工資扣除一個相同的量。我真不知道除了調工資他還做什麼其它事情。

工資的頻繁調整很讓員工反感，尤其是集體扣除工資的時候，一旦某位員工發現自己的工資已經低于了合同規定的工資下界，他就會立刻氣憤地離開公司，并且再也不會回來了。每位員工的工資下界都是統一規定的。每當一個人離開公司，我就要從電腦中把他的工資檔案删去，同樣，每當公司招聘了一位新員工，我就得為他建立一個工資檔案。

老闆經常到我這邊來詢問工資情況，他并不問具體某位員工的工資情況，而是問現在工資第k多的員工拿多少工資。每當這時，我就不得不對數萬個員工進行一次漫長的排序，然後告訴他答案。

好了，現在你已經對我的工作了解不少了。正如你猜的那樣，我想請你編一個工資統計程式。怎麼樣，不是很困難吧？

如果某個員工的初始工資低于最低工資标準,那麼将不計入最後的答案内

輸入輸出格式

輸入格式：

第一行有兩個非負整數n和min。n表示下面有多少條指令，min表示工資下界。

接下來的n行，每行表示一條指令。指令可以是以下四種之一：

名稱 格式 作用

I指令 I_k 建立一個工資檔案，初始工資為k。如果某員工的初始工資低于工資下界，他将立刻離開公司。

A指令 A_k 把每位員工的工資加上k

S指令 S_k 把每位員工的工資扣除k

F指令 F_k 查詢第k多的工資

_（下劃線）表示一個空格，I指令、A指令、S指令中的k是一個非負整數，F指令中的k是一個正整數。

在初始時，可以認為公司裡一個員工也沒有。

輸出格式：

輸出檔案的行數為F指令的條數加一。

對于每條F指令，你的程式要輸出一行，僅包含一個整數，為目前工資第k多的員工所拿的工資數，如果k大于目前員工的數目，則輸出-1。

輸出檔案的最後一行包含一個整數，為離開公司的員工的總數。

輸入輸出樣例

輸入樣例#1： 複制

9 10

I 60

I 70

S 50

F 2

I 30

S 15

A 5

F 1

輸出樣例#1： 複制

10

20

-1

2

說明

I指令的條數不超過100000

A指令和S指令的總條數不超過100

F指令的條數不超過100000

每次工資調整的調整量不超過1000

新員工的工資不超過100000

題解：先講講做法

假設你會splay，然後就變的很簡單了

我們記錄一個now為現在被減去了多少（正減負加）

顯然插入操作是往splay中插入vx+now

a隻需要将now減掉val

s将now加val并且将值小于min+now的所有點删掉

具體做法是找到min+now的前驅的後繼，将它splay到根，将它的左子樹置為0

f找到第k大，并輸出val-now

以下是菜雞的寫題心路曆程

沒錯，這題我寫了一天。

最初的時候的确是寫錯了第k大部分，然後我問czl linux有沒有sleep

czl表示沒有

然後我說這個簡單啊，我在裡面加個超級大的for循環不就行了嗎？

接着我很快就調出了k大哪裡寫萎了，過了樣例我就交了。

結果隻過了1個點，其他點都T飛

調了一個下午，突然發現，嗯？這裡怎麼會有個for循環？？？

删掉，過了。。。。。。

我到底是有多菜啊qwq

代碼如下：

#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson ch[x][0]
#define rson ch[x][1]
#define hi puts("hi!");
using namespace std;
 
int f[100010],ch[100010][2],key[100010],cnt[100010],size[100010],pos,rt,sz,now,tot,m,min1,val,ans;
 
int push_up(int x)
{
    size[x]=size[lson]+size[rson]+cnt[x];
}
 
int rotate(int x)
{
    int y=f[x],z=f[y],kd=ch[y][1]==x,xs=ch[x][!kd];
    if(z) ch[z][ch[z][1]==y]=x;
    ch[y][kd]=xs;
    ch[x][!kd]=y;
    if(xs) f[xs]=y;
    f[x]=z;
    f[y]=x;
    push_up(y);
}
 
int splay(int x,int goal)
{
    int y,z;
    while(f[x]!=goal)
    {
        y=f[x],z=f[y];
        if(z!=goal) (ch[z][1]==y)^(ch[y][1]==x)?rotate(x):rotate(y);
        rotate(x);
    }
    push_up(x);
    if(!goal) rt=x;
}
 
int find(int x)
{
    pos=rt;
    while(key[pos]!=x)
    {
        if(key[pos]>x)
        {
            if(ch[pos][0]) pos=ch[pos][0];
            else break;
        }
        else
        {
            if(ch[pos][1]) pos=ch[pos][1];
            else break;
        }
    }
}
 
int insert(int x)
{
    find(x);
    if(key[pos]==x) cnt[pos]++,size[pos]++;
    else
    {
        cnt[++sz]=1,key[sz]=x,size[sz]=1;
        if(key[pos]>x) f[sz]=pos,ch[pos][0]=pos?sz:0,pos=sz;
        else f[sz]=pos,ch[pos][1]=pos?sz:0,pos=sz;
    }
    splay(pos,0);
}
 
int get(int x,int kd)
{
    find(x);
    if(kd&&key[pos]>x) return 0;
    if((!kd)&&key[pos]<x) return 0;
    splay(pos,0);
    pos=ch[pos][kd];
    while(ch[pos][!kd]) pos=ch[pos][!kd];
    return 0;
}
 
int del()
{
    int sum=min1+now;
    get(sum,0);
    get(key[pos],1);
    splay(pos,0);
    ans+=size[ch[pos][0]]-1;
    ch[pos][0]=0;
    push_up(pos);
}
 
int kth(int k) 
{
    pos=rt;
    while(size[ch[pos][0]]>=k||size[ch[pos][0]]+cnt[pos]<k)
    {
        if(size[ch[pos][0]]>=k&&ch[pos][0]) pos=ch[pos][0];
        else if(k>size[ch[pos][0]]+cnt[pos]&&ch[pos][1]) k-=cnt[pos]+size[ch[pos][0]],pos=ch[pos][1];
    }
}
 
int print(int x)
{
    if(lson) print(lson);
    if(rson) print(rson);
    printf("%d %d %d\n",key[x],key[lson],key[rson]);
}
 
char op[20];
 
int main()
{
    insert(-1e9);
    insert(1e9);
    scanf("%d%d",&m,&min1);
    int tmpp=m;
    while(m--)
    {
        scanf("%s%d",op,&val);
        if(op[0]=='I') if(val>=min1) insert(val+now);
        if(op[0]=='A') now-=val;
        if(op[0]=='S') now+=val,del(),insert(-1e9);
        if(op[0]=='F')
        {
            if(val>size[rt]-2) puts("-1");
            else kth(size[rt]-val),printf("%d\n",key[pos]-now);
        }
    }
    printf("%d\n",ans);
}