Description
Solution
显然是用平衡树维护，感觉 Splay 比较好维护。
设 \(delta\) 表示当前总共加了多少工资，\(delta < 0\) 则表示扣了 \(-delta\) 的工资。
对于 I 操作，直接在平衡树里插入 \(k-delta\)。
对于 A 操作，就将 \(delta\) 加 \(k\)。
对于 S 操作，这时可能会有一些员工离开公司，所以可以先把 \(minn-delta\) 插入到平衡树，并将其 splay 到根节点，这样左子树就是要去除的，直接将 ch[rt][0] 赋为 0，然后再删除 \(minn-delta\)。剩下的就是还能留在公司的。
对于询问，如果平衡树里的结点个数不少于 \(k\) 就直接求即可，否则输出 \(-1\)。注意：这是求第 \(k\) 大的值！（我在询问里把平衡树里的结点个数写成了进入过公司的员工个数，导致样例 TLE。）
这样就可以做到均摊 \(O(\log n)\) 的时间复杂度。
Code
代码
#include <bits/stdc++.h>
#ifdef ORZXKR
#include <debug.h>
#else
#define debug(...) 1
#endif
using namespace std;
const int kMaxN = 1e5 + 5;
class Splay {
public:
void pushup(int x) {
sz[x] = sz[ch[x][0]] + cnt[x] + sz[ch[x][1]];
}
int get(int x) {
return x == ch[fa[x]][1];
}
void clear(int x) {
fa[x] = ch[x][0] = ch[x][1] = sz[x] = val[x] = cnt[x] = 0;
}
int newnode(int x) {
val[++tot] = x, cnt[tot] = sz[tot] = 1;
return tot;
}
void rotate(int x) {
int fl = get(x), y = fa[x], z = fa[y];
if (ch[x][fl ^ 1]) fa[ch[x][fl ^ 1]] = y;
ch[y][fl] = ch[x][fl ^ 1], ch[x][fl ^ 1] = y;
if (z) ch[z][get(y)] = x;
fa[y] = x, fa[x] = z;
pushup(y), pushup(x);
}
void splay(int x) {
for (int y = fa[x]; y; rotate(x), y = fa[x]) {
if (fa[y]) rotate(get(x) == get(y) ? y : x);
}
rt = x;
}
void ins(int x) {
if (!rt) {
rt = newnode(x);
return ;
}
for (int cur = rt, f = 0; ; ) {
if (val[cur] == x) {
++cnt[cur], pushup(cur), pushup(f);
return splay(cur);
}
f = cur;
cur = ch[cur][val[cur] < x];
if (!cur) {
cur = newnode(x), fa[cur] = f, ch[f][val[f] < x] = cur;
return pushup(cur), pushup(f), splay(cur);
}
}
}
int getrk(int x) {
int ret = 0;
for (int cur = rt; cur; ) {
if (x < val[cur]) {
cur = ch[cur][0];
} else if (x == val[cur]) {
ret += sz[ch[cur][0]] + cnt[cur];
return splay(cur), ret;
} else {
ret += sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
}
}
return ret;
}
int getkth(int x) {
for (int cur = rt; ; ) {
if (x <= sz[ch[cur][0]]) {
cur = ch[cur][0];
} else if (x <= sz[ch[cur][0]] + cnt[cur]) {
return splay(cur), val[cur];
} else {
x -= sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
}
}
}
void _getpre() {
int cur = ch[rt][0];
for (; ch[cur][1]; cur = ch[cur][1]) {}
splay(cur);
}
void del(int x) {
getrk(x);
if (cnt[rt] > 1) {
--cnt[rt], pushup(rt);
return ;
}
if (!ch[rt][0] && !ch[rt][1]) {
clear(rt), rt = 0;
return ;
} else if (!ch[rt][0]) {
int tmp = rt; rt = ch[rt][1];
return fa[rt] = 0, clear(tmp);
} else if (!ch[rt][1]) {
int tmp = rt; rt = ch[rt][0];
return fa[rt] = 0, clear(tmp);
}
int oldrt = rt; _getpre();
ch[rt][1] = ch[oldrt][1], fa[ch[oldrt][1]] = rt;
clear(oldrt);
return pushup(rt);
}
void yxy() {
ch[rt][0] = 0, pushup(rt);
}
int gettot() {
return sz[rt];
}
public:
int rt, tot, fa[kMaxN], ch[kMaxN][2], sz[kMaxN], val[kMaxN], cnt[kMaxN];
} s;
int n, mini, nw, k, tot, delta;
char op[10];
int main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d%d", &n, &mini);
for (int i = 1; i <= n; ++i) {
scanf("%s%d", op, &k);
if (op[0] == 'I') { // INSERT
if (k < mini) continue ;
++tot, s.ins(k - delta);
} else if (op[0] == 'A') { // ADD
delta += k;
} else if (op[0] == 'S') { // MINUS
delta -= k;
s.ins(mini - delta), s.yxy(), s.del(mini - delta);
} else { // QUERY
int sz = s.gettot();
if (sz >= k) printf("%d\n", s.getkth(sz - k + 1) + delta);
else puts("-1");
}
}
printf("%d\n", tot - s.gettot());
return 0;
}