题目链接
维护四个操作
-
I k 新建一个工资档案，初始工资为 k。如果某员工的初始工资低于工资下界，他将立刻离开公司。
-
A k 把每位员工的工资加上k 。
-
S k 把每位员工的工资扣除 k。
-
F k 查询第 k 多的工资。
对于A和S操作，我们直接用一个值lazy来记录所有数变化是多少，当插入一个数的时侯我们改为插入k-lazy。k小于min的不加入，查询第k多的记得加上lazy。删除操作就直接分裂然后删除即可，记录每次删除的数的个数。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
template <typename T> inline void read(T &x) {
x = 0; T f = 1;char s = getchar();for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);x *= f;}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i > (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
int val[N], siz[N], ch[N][2], rnd[N];
int Min, lazy, cnt, root;int new_node(int x){
val[++cnt] = x;siz[cnt] = 1;rnd[cnt] = rand();return cnt;
}
void up(int rt) {
siz[rt] = 1 + siz[ch[rt][0]] + siz[ch[rt][1]];
}
void split(int rt, int k, int &x, int &y) {
if(!rt) return x = y = 0, void (0);if(val[rt] <= k) {
x = rt; split(ch[rt][1], k, ch[rt][1], y);} else {
y = rt; split(ch[rt][0], k, x, ch[rt][0]);}up(rt);
}
int merge(int x, int y) {
if(!x || !y) return x ^ y;if(rnd[x] < rnd[y]) {
ch[x][1] = merge(ch[x][1], y);up(x); return x;} ch[y][0] = merge(x, ch[y][0]);up(y); return y;
}
int x, y;
void insert(int a) {
split(root, a-1, x, y);root = merge(merge(x, new_node(a)), y);
}
int num;
void del() {
split(root, Min-lazy-1, x, root);num += siz[x];
}
int _kth(int rt, int k) {
if(siz[rt] < k) return -1;while(rt) {
if(k <= siz[ch[rt][1]]) rt = ch[rt][1];else if(k == siz[ch[rt][1]] + 1) return val[rt] + lazy;else k -= siz[ch[rt][1]] + 1, rt = ch[rt][0];}
}
int main() {
srand(time(0));int n, k; read(n); read(Min);char op[2];while(n--) {
scanf("%s %d", op, &k);switch(op[0]) {
case 'I':if(k < Min) continue;insert(k-lazy);break;case 'A':lazy += k;break;case 'S':lazy -= k;del();break;case 'F':printf("%d\n", _kth(root, k));break;}}printf("%d\n", num);
}