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;
}