题目链接
维护四个操作
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); }