$$\LARGE{\color{purple}{\mathbf{Note-算法进阶课} } }$$
郁闷的出纳员
splay的基本函数可以参考
0. 题面简述
本题要求设计数据结构能够满足:
1. 给每一个员工的工资加上 $k$
2. 给每一个员工的工资减去 $k$
3. 在数据结构插入一个新员工,且其初始工资为 $k$
4. 剩余员工内,查询工资第 $k$ 大的工资是多少
另外满足:
1. 员工入职时,低于给定的工资下界,员工当场离职
2. 当老板扣员工工资,使得某个员工工资低于给定的工资下界,员工离职
1. 一点分析
由于涉及到查询第 $k$ 大以及删除整个区间,线段树难以实现(具体来说是难以实现删除区间的操作)
这里需要使用支持维护区间的平衡树来做–$splay$
2. 一些细节
2.1. $\color{Red}{\mathsf{使用偏移量 delta 维护所有员工的工资变化}}$
那么我们插入时,设员工工资真实值为 $k$,我们需要使用 $insert(k - delta)$
这样所有员工的工资就是 $splay$ 中维护的 $v$ 再加上 $delta$
2.2. $\color{purple}{\mathsf{使用两个哨兵节点(可以只是一个,但是为了追求对称)}} $
删除工资位于 $(-INF,m - delta)$ 的节点(m : 员工容许的工资下界)
插入哨兵节点 L 使得 $L.v = -INF$ ,然后按照关键字找到 R(R 是最小的满足关键字大于等于 $m - delta$的节点)
splay(R,0),splay(L,R)后
{:height=”20%” width=”20%”class=”img-responsive”}
三角形区域即我们要删除的$(-INF,m - delta)$区间,将此时的 L 节点的右儿子清空即可
2.3. $\color{green}{\mathsf{查询第 k 大}} $
这个可以在查询第 $k$ 小的函数基础上稍微改一下即可,可以参考下面写的 kth 函数
注意插入了一个哨兵节点(INF),所以实际上我们查询的是第k + 1大值
ps:维护第 $k$ 小(大),需要先维护以节点为根的树的节点总个数 ($sz$)
输出总共离职人数可以用入职人数($tot$)减去最后剩余员工数量($sz$)
splay
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 100010;
constexpr int INF = 1E9;
int delta;// 维护偏移量
struct Node
{
int s[2],v,p;
int sz;
void init(int _v,int _p)
{
v = _v,p = _p,sz = 1;
}
}tr[N];
int root,idx;
void pushup(int u)
{
tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + 1;
}
void rotate(int x)
{
int y = tr[x].p,z = tr[y].p;
int k = (x == tr[y].s[1]);
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y),pushup(x);
}
void splay(int x,int k)
{
while(tr[x].p != k)
{
int y = tr[x].p,z = tr[y].p;
if(z != k)
{
if((tr[y].s[1] == x) ^ (tr[z].s[1] == x)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root = x;
}
int insert(int x)
{
int u = root,p = 0;
while(u) p = u,u = tr[u].s[x > tr[u].v];
u = ++ idx;
if(p) tr[p].s[x > tr[p].v] = u;
tr[u].init(x,p);
splay(u,0);
return u;
}
int find(int v)// 查找值>= v的节点
{
int u = root,res;
while(u)
{
if(tr[u].v >= v) res = u,u = tr[u].s[0];
else u = tr[u].s[1];
}
return res;
}
int kth(int k)// 查找第k大
{
int u = root;
while(u)
{
if(tr[tr[u].s[1]].sz >= k) u = tr[u].s[1];
else if(tr[tr[u].s[1]].sz + 1 == k) return u;
else k -= tr[tr[u].s[1]].sz + 1,u = tr[u].s[0];
}
return -1;
}
int main()
{
fastio();
int n,m,tot = 0;
cin >> n >> m;
int L = insert(-INF),R = insert(INF);
while(n -- )
{
int x;
char op[2];
cin >> op >> x;
if(*op == 'I')
{
if(x >= m) insert(x - delta),tot ++ ;
}
else if(*op == 'A') delta += x;
else if(*op == 'S')
{
delta -= x;
R = find(m - delta);
splay(R,0),splay(L,R);
tr[L].s[1] = 0;
pushup(L),pushup(R);
}
else
{
if(x > tr[root].sz - 2) cout << -1 << endl;
else cout << tr[kth(x + 1)].v + delta << endl;
}
}
cout << tot - (tr[root].sz - 2) << endl;
}