%%%
@[lrj124](/space/show?uid=17521)
by hellomath @ 2018-03-06 00:15:43
@[lrj124](/space/show?uid=17521) 我的代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct Splay {
int tot, root, ch[maxn][2], fa[maxn], val[maxn], size[maxn], cnt[maxn];
void maintain(int k) {
size[k] = size[ch[k][0]] + size[ch[k][1]] + cnt[k];
}
bool get(int k) {
return k == ch[fa[k]][1];
}
void clear(int k) {
ch[k][0] = ch[k][1] = fa[k] = val[k] = size[k] = cnt[k] = 0;
}
void rotate(int k) {
int old = fa[k], oldf = fa[old], chk = get(k);
ch[old][chk] = ch[k][chk ^ 1];
fa[ch[old][chk]] = old;
ch[k][chk ^ 1] = old;
fa[old] = k;
fa[k] = oldf;
if (oldf) {
ch[oldf][ch[oldf][1] == old] = k;
}
maintain(old), maintain(k);
}
void splay(int k) {
for (int f = fa[k]; f = fa[k]; rotate(k)) {
if (fa[f]) {
rotate(get(k) == get(f) ? f : k);
}
}
root = k;
}
void insert(int k) {
if (!root) {
val[++tot] = k;
cnt[tot]++;
root = tot;
maintain(root);
return;
}
int cur = root, f = 0;
while (1) {
if (val[cur] == k) {
cnt[cur]++;
maintain(cur), maintain(f);
splay(cur);
break;
}
f = cur;
cur = ch[cur][val[cur] < k];
if (!cur) {
val[++tot] = k;
cnt[tot]++;
fa[tot] = f;
ch[f][val[f] < k] = tot;
maintain(tot), maintain(f);
splay(tot);
break;
}
}
}
int rk(int k) {
int res = 0, cur = root;
while (1) {
if (k < val[cur]) {
cur = ch[cur][0];
} else {
res += size[ch[cur][0]];
if (k == val[cur]) {
splay(cur);
return res + 1;
}
res += cnt[cur];
cur = ch[cur][1];
}
}
}
int kth(int k) {
int cur = root;
while (1) {
if (ch[cur][0] && k <= size[ch[cur][0]]) {
cur = ch[cur][0];
} else {
k -= cnt[cur] + size[ch[cur][0]];
if (k <= 0) {
return val[cur];
}
cur = ch[cur][1];
}
}
}
int get_prev() {
int cur = ch[root][0];
while (ch[cur][1]) {
cur = ch[cur][1];
}
return cur;
}
void del(int k) {
rk(k);
if (cnt[root] > 1) {
cnt[root]--;
maintain(root);
return;
}
if (!ch[root][0] && !ch[root][1]) {
clear(root);
root = 0;
return;
}
if (!ch[root][0]) {
int old = root;
root = ch[root][1];
fa[root] = 0;
clear(old);
return;
}
if (!ch[root][1]) {
int old = root;
root = ch[root][0];
fa[root] = 0;
clear(old);
return;
}
int x = get_prev(), old = root;
splay(x);
fa[ch[old][1]] = x;
ch[x][1] = ch[old][1];
clear(old);
maintain(root);
}
} tree;
int main() {
int n, mn, add = 0, cnt = 0;
scanf("%d %d", &n, &mn);
while (n--) {
char op;
int k, sz = tree.size[tree.root];
scanf("\n%c %d", &op, &k);
if (op == 'I') {
if (k >= mn) {
tree.insert(k - add);
}
} else if (op == 'A') {
add += k;
} else if (op == 'S') {
add -= k;
for (int i = 1; i <= sz; i++) {
if (tree.kth(1) + add < mn) {
tree.del(tree.kth(1));
cnt++;
} else {
break;
}
}
} else {
printf("%d\n", k > sz ? -1 : tree.kth(sz - k + 1) + add);
}
}
printf("%d\n", cnt);
return 0;
}
```
by hellomath @ 2018-03-06 00:16:59
@[larryzhong](/space/show?uid=20438) %%%按您的代码每次工资下降所有的都看一遍A了qwq，我之前那个是hzwer的做法qwq
by lrj124 @ 2018-03-06 22:59:28