Skip to content

11054: 【原1054】郁闷的二哥

题目

题目描述

author: 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1054

Description

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

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

老板经常到二哥这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,二哥就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。

好了,现在你已经对二哥的工作了解不少了。正如你猜的那样,二哥想请你编一个工资统计程序。怎么样,不是很困难吧?

Input Format

第一行有两个非负整数n和min。n表示下面有多少条命令,min表示工资下界。

接下来的n行,每行表示一条命令。命令可以是以下四种之一:

(Here put the table)

_(下划线)表示一个空格,I命令、A命令、S命令中的k是一个非负整数,F命令中的k是一个正整数。

在初始时,可以认为公司里一个员工也没有。

Output Format

输出文件的行数为F命令的条数加一。

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

输出文件的最后一行包含一个整数,为离开公司的员工的总数。

说明

NOI 2004 cashier

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

FineArtz's solution

/* 郁闷的二哥 */
#include <iostream>
using namespace std;

class Node{
public:
    Node *p = nullptr, *s[2] = {nullptr, nullptr};
    int key = 0, size = 1, num = 1;

    Node(int k) : key(k) { p = s[0] = s[1] = nullptr; size = 1; num = 1; }
    bool whichChild() { return p->s[1] == this; }
    Node *link(int w, Node *x){
        s[w] = x;
        if (x)
            x->p = this;
        return this;
    }
    void update(){
        size = num + (s[0] ? s[0]->size : 0) + (s[1] ? s[1]->size : 0);
    }
};

Node *root = nullptr;
int ans = 0;

void rotate(Node *p){
    Node *q = p->p->p;
    if (p->whichChild())
        p->link(0, p->p->link(1, p->s[0]));
    else
        p->link(1, p->p->link(0, p->s[1]));
    p->p->update();
    if (q)
        q->link(q->s[1] == p->p, p);
    else{
        p->p = nullptr;
        root = p;
    }
}

void splay(Node *p, Node *t = nullptr){
    while (p->p != t && p->p->p != t){
        if (p->whichChild() == p->p->whichChild()){
            rotate(p->p);
            rotate(p);
        }
        else{
            rotate(p);
            rotate(p);
        }
    }
    if (p->p != t)
        rotate(p);
    p->update();
}

Node *find(int x){
    Node *p = root;
    while (p && p->key != x)
        p = p->s[p->key < x];
    if (p)
        splay(p);
    return p;
}

void insert(int x){
    if (!root){
        root = new Node(x);
        return;
    }
    if (find(x)){
        ++root->num;
        root->update();
        return;
    }
    Node *p = root, *q;
    while (p){
        q = p;
        p = p->s[p->key < x];
    }
    p = new Node(x);
    q->link(q->key < x, p);
    splay(p);
}

Node *findk(int k){
    if (root->size < k)
        return nullptr;
    Node *p = root;
    while (!(((p->s[0] ? p->s[0]->size : 0) < k) && ((p->s[0] ? p->s[0]->size : 0) + p->num >= k))){
        if (!p->s[0]){
            k -= p->num;
            p = p->s[1];
        }
        else{
            if (p->s[0]->size >= k)
                p = p->s[0];
            else{
                k -= (p->s[0]->size + p->num);
                p = p->s[1];
            }
        }
    }
    if (p)
        splay(p);
    return p;
}

Node *prev(){
    Node *p = root->s[0];
    if (!p)
        return nullptr;
    while (p->s[1])
        p = p->s[1];
    splay(p);
    return p;
}

Node *succ(){
    Node *p = root->s[1];
    if (!p)
        return nullptr;
    while (p->s[0])
        p = p->s[0];
    splay(p);
    return p;
}

void del(int l, int r){
    if (!find(l)){
        insert(l);
        --ans;
    }
    Node *p = prev();
    if (!find(r)){
        insert(r);
        --ans;
    }
    Node *q = succ();
    if (!p && !q){
        ans += root->size;
        root = nullptr;
        return;
    }
    if (!p){
        if (root->s[0])
            ans += root->s[0]->size;
        root->s[0] = nullptr;
        root->update();
        return;
    }
    if (!q){
        splay(p, 0);
        if (root->s[1])
            ans += root->s[1]->size;
        root->s[1] = nullptr;
        root->update();
        return;
    }
    splay(p, q);
    if (p->s[1])
        ans += p->s[1]->size;
    p->s[1] = nullptr;
    p->update();
    q->update();
}

void dispose(Node *p){
    if (!p) return;
    dispose(p->s[0]);
    dispose(p->s[1]);
    delete p;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, delta = 0;
    cin >> n >> m;
    while (n--){
        char ch;
        int k;
        cin >> ch >> k;
        switch(ch){
        case 'I':
            if (k >= m) insert(k - delta);
            break;
        case 'A':
            delta += k;
            break;
        case 'S':
            delta -= k;
            del(-1000000, m - delta - 1);
            break;
        case 'F':
            if (!root || root->size < k)
                cout << "-1\n";
            else{
                findk(root->size + 1 - k);
                cout << root->key + delta << '\n';
            }
            break;
        }
    }
    dispose(root);
    cout << ans << '\n';
    return 0;
}

yyong119's solution

#include <cstdio>
using namespace std;
const int MAX_N = 100010;
struct node {
    long size, right, left, key;
}tree[MAX_N];
long tt, t, minwage, deltawage;

void right_rotate(long& t) {

    long tmp = tree[t].left;
    tree[t].left = tree[tmp].right;
    tree[tmp].right = t;
    tree[tmp].size = tree[t].size;
    tree[t].size = tree[tree[t].left].size + tree[tree[t].right].size + 1;
    t = tmp;
}

void left_rotate(long& t) {

    long tmp = tree[t].right;
    tree[t].right = tree[tmp].left;
    tree[tmp].left = t;
    tree[tmp].size = tree[t].size;
    tree[t].size = tree[tree[t].left].size + tree[tree[t].right].size + 1;
    t = tmp;
}

void maintain(long& t, bool flag) {

    if (!flag) {
        if (tree[tree[tree[t].left].left].size > tree[tree[t].right].size)
            right_rotate(t);
        else if (tree[tree[tree[t].left].right].size > tree[tree[t].right].size) {
            left_rotate(tree[t].left);
            right_rotate(t);
        }
        else return;
    }
    else {
        if (tree[tree[tree[t].right].right].size > tree[tree[t].left].size)
            left_rotate(t);
        else if (tree[tree[tree[t].right].left].size > tree[tree[t].left].size) {
            right_rotate(tree[t].right);
            left_rotate(t);
        }
        else return;
    }
    maintain(tree[t].left, false);
    maintain(tree[t].right, true);
    maintain(t, true);
    maintain(t, false);
}

void insertnum(long& t, long value) {

    if (t == 0) {
        t = ++tt;
        tree[t].key = value;
        tree[t].size = 1;
    }
    else {
        ++tree[t].size;
        if (value >= tree[t].key) insertnum(tree[t].right, value);
        else insertnum(tree[t].left, value);
        maintain(t, value >= tree[t].key);
    }
}
void deletenum(long& t) {

    if (t == 0) return;
    if (tree[t].key + deltawage >= minwage) {
        deletenum(tree[t].left);
        tree[t].size = tree[tree[t].left].size + tree[tree[t].right].size + 1;
    }
    else {
        t = tree[t].right;
        deletenum(t);
    }
}

long select(long& t, long k) {

    if (tree[tree[t].right].size + 1 == k) return t;
    if (tree[tree[t].right].size + 1 >= k) return select(tree[t].right, k);
    else return select(tree[t].left, k - tree[tree[t].right].size - 1);
}

int main() {

    int n, tmp;
    char op[10];
    scanf("%d%ld", &n, &minwage);
    while (n--) {
        scanf("%s%d", &op, &tmp);
        switch (op[0]) {
            case 'I':
                if (tmp >= minwage) insertnum(t, tmp - deltawage);
                break;
            case 'A':
                deltawage += tmp;
                break;
            case 'S':
                deltawage -= tmp;
                deletenum(t);
                break;
            case 'F':
                if (tmp > tree[t].size) printf("%d\n", -1);
                else printf("%ld\n", deltawage + tree[select(t, tmp)].key);
                break;
        }
    }
    printf("%ld", tt - tree[t].size);
    return 0;
}