BZOJ1503【NOI2004】郁闷的出纳员 < Splay >

Posted on Symbols count in article: 1.5k Reading time ≈ 6 mins.

Problem

【NOI2004】郁闷的出纳员

Time  Limit:  5  Sec\mathrm{Time\;Limit:\;5\;Sec}
Memory  Limit:  64  MB\mathrm{Memory\;Limit:\;64\;MB}

Description

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

Input

第一行有两个非负整数nn和minmin。nn表示下面有多少条命令，minmin表示工资下界。
接下来的nn行，每行表示一条命令。命令可以是以下四种之一：

名称 格式 作用
I\mathrm{I}命令 I  kI\;k 新建一个工资档案，初始工资为kk
A\mathrm{A}命令 A  kA\;k 把每位员工的工资加上kk
S\mathrm{S}命令 S  kS\;k 把每位员工的工资扣除kk
F\mathrm{F}命令 F  kF\;k 查询第kk多的工资

I\mathrm{I}命令、A\mathrm{A}命令、S\mathrm{S}命令中的kk是一个非负整数，F\mathrm{F}命令中的kk是一个正整数。
在初始时，可以认为公司里一个员工也没有。
I\mathrm{I}命令的条数不超过10510^5
A\mathrm{A}命令和S\mathrm{S}命令的总条数不超过100100
F\mathrm{F}命令的条数不超过10510^5
每次工资调整的调整量不超过10001000
新员工的工资不超过10510^5

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
10
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

Sample Output

1
2
3
4
10
20
-1
2

标签：Splay

Solution

Splay\mathrm{Splay}基础题。

由于加和减都是作用于全局，我们可以单独记当前加和减操作造成的总偏差是多少，记为detdet，即当前序列中每个数的真实值为其在序列中的值加detdet。这样新加入一个大小为xx的数时，相当于在序列中加入一个大小为x−detx-det的数。
对于每个I\mathrm{I}命令，在Splay\mathrm{Splay}中插入一个数x−detx-det。
对于每个A\mathrm{A}命令，det=det+xdet=det+x。
对于每个S\mathrm{S}命令，det=det−xdet=det-x，再将序列中所有小于min−detmin-det的数删除。具体地，将保护结点−∞-\infty转到根，将min−det−1min-det-1的后继结点转到根的右儿子，将根的右儿子的左儿子整体删除。
对于每个F\mathrm{F}命令，询问第xx小的值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define flag cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, mi, det, tot;
struct SplayNode {
    SplayNode *s[2], *fa; int val, w, sz;
    void update() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
} ;
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->w = v->sz = 1;
        return v;
    }
    SplayTree() {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->update();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->update(), v->update();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if (flag) rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        int lsz = v->s[0] ? v->s[0]->sz : 0;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+v->w) return get_kth(v->s[1], k-lsz-v->w);
        return v;
    }
    void insert(int _val) {
        if (_val+det < mi) return;
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->update(), rt->update();
    }
    void remove(int _val) {
        SplayNode* pre = get_kth(rt, 1);
        SplayNode* suc = successor(_val-1);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) tot += suc->s[0]->sz;
        suc->s[0] = NULL, suc->update(), rt->update();
    }
} BBST;
int main() {
    read(n), read(mi);
    for (int x; n; n--) {
        char opt[1]; scanf("%s", opt), read(x);
        if (opt[0] == 'I') BBST.insert(x-det);
        if (opt[0] == 'A') det += x;
        if (opt[0] == 'S') BBST.remove(mi-(det-=x));
        if (opt[0] == 'F') {
            x = BBST.rt->sz-x-1;
            if (x < 1 || x > BBST.rt->sz-2) puts("-1");
            else printf("%d\n", BBST.get_kth(BBST.rt, x+1)->val+det);
        }
    }
    return printf("%d\n", tot), 0;
}