[ZJ][線段樹][懶操作] a126. NOI2004 Day1.1.郁闷的出纳员
內容 ：
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。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。範例輸入 ：
9 10 I 60 I 70 S 50 F 2 I 30 S 15 A 5 F 1 F 2
範例輸出 ：
10 20 -1 2
提示
：
l 新员工的工资不超过100000
//这里提醒一点，题目中有说【如果某员工的初始工资低于工资下界，他将立刻离开公司。】，这里不计入离开公司的总人数！我也在这里WA了好久......
——liouzhou_101注
出處
：
我被一個 S 0 害了 RE。
這題要算一下陣列的大小，就以測資來看浮動範圍是 10 萬，因此要開 30 萬格。
然後從基線 10 萬開始做調整。
遞迴與非遞迴以及 zkw 的想法都混雜了。
/**********************************************************************************/
/* Problem: a126 "NOI2004 Day1.1.郁闷的出纳员" from NOI2004 Day1 第一题 */
/* Language: CPP (2780 Bytes) */
/* Result: AC(36ms, 5.4MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-05 11:07:47 */
/**********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
int ST[1048577], M, N = 300005;
char CLR[1048577];
void setST() {
for(M = 1; M < N+2; M <<= 1);
int i;
for(i = 2*M-1; i >= M; i--)
ST[i] = 0, CLR[i] = 0;
for(i = M-1; i > 0; i--)
ST[i] = ST[i<<1]+ST[i<<1|1], CLR[i] = 0;
}
int relax(int k) {
if(CLR[k]) {
CLR[k] = 0;
if(k < M) {
ST[k<<1] = ST[k<<1|1] = 0;
CLR[k<<1] = CLR[k<<1|1] = 1;
}
}
}
int query(int l, int r, int x, int y, int k) {
relax(k);
int m = (l+r)>>1;
if(l == x && r == y)
return ST[k];
if(x > m)
return query(m+1, r, x, y, k<<1|1);
else if(y <= m)
return query(l, m, x, y, k<<1);
else
return query(l, m, x, m, k<<1)+
query(m+1, r, m+1, y, k<<1|1);
} // query(1, M, x, y, 1)
void modifyCLR(int l, int r, int x, int y, int k) {
relax(k);
int m = (l+r)>>1;
if(l == x && r == y) {
CLR[k] = 1, ST[k] = 0;
return ;
}
if(x > m)
modifyCLR(m+1, r, x, y, k<<1|1);
else if(y <= m)
modifyCLR(l, m, x, y, k<<1);
else
modifyCLR(l, m, x, m, k<<1), modifyCLR(m+1, r, m+1, y, k<<1|1);
ST[k] = ST[k<<1] + ST[k<<1|1];
}
void modify(int s, int val) {
static int t, l, r, m;
t = 1;
l = 0, r = M-1;
do {
relax(t);
ST[t] += val;
m = (l+r)>>1;
if(m < s)
t = t<<1|1, l = m+1;
else
t <<= 1, r = m;
} while(t < 2*M);
}
int main() {
setST();
int n, mn, arg;
int base_line = 100005;
int tot = 0, leave = 0, tmp;
char cmd[20];
scanf("%d %d", &n, &mn);
while(n--) {
scanf("%s %d", cmd, &arg);
if(cmd[0] == 'I') {
if(arg >= mn) {
modify(arg+base_line, 1), tot++;
}
} else if(cmd[0] == 'A') {
base_line -= arg; // 基線下降
} else if(cmd[0] == 'S') {
if(arg == 0) continue;
tmp = query(0, M-1, base_line, base_line+arg+mn-1, 1);
tot -= tmp, leave += tmp;
modifyCLR(0, M-1, base_line, base_line+arg+mn-1, 1);
base_line += arg; // 基線上升
} else {
if(tot < arg) {
puts("-1");
continue;
}
int s;
arg = tot-arg+1;
for(s = 1; s < M;) {
relax(s);
if(ST[s<<1] < arg)
arg -= ST[s<<1], s = s<<1|1;
else
s = s<<1;
}
printf("%d\n", s-M-base_line);
}
}
printf("%d\n", leave);
return 0;
}