Steven_MengのBlog

传送门
这道题比较有意思
考虑记录一个$tag$表示员工工资应该加上多少。
加工资的操作不会导致员工离开
但是扣工资的操作会导致工资所有小于$min-tag$的员工离开

怎么删除所有小于$min-tag$的值呢?
yy一下,发现FHQ Treap中$num$左子树的值都小于num
于是每次删除所有小于$min-tag$的值时,删除其左子树即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 500005
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
namespace FHQ_Treap{
struct node{
int l,r;
int val;//每个点的权值
int pri;//优先级(随机生成)
int sz;
}tree[MAXN];
int tot;
#define lc(i) tree[i].l
#define rc(i) tree[i].r
inline void Update(int x){
tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
}
inline int New(int v){
tree[++tot].val=v;
tree[tot].pri=rand();
tree[tot].sz=1;
return tot;
}
int Merge(int x,int y){
if (!x||!y) return x+y;
if (tree[x].pri<tree[y].pri){
rc(x)=Merge(rc(x),y),Update(x);
return x;
}
else {
lc(y)=Merge(x,lc(y)),Update(y);
return y;
}
}
void Split(int i,int k,int &x,int &y){
if (!i){//叶节点
x=y=0;
}
else {
if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);}
else{y=i,Split(lc(i),k,x,lc(i));}
Update(i);
}
}
int kth(int i,int k){//排名为k
while (true){
if (k<=tree[lc(i)].sz){
i=lc(i);
}
else if (k==tree[lc(i)].sz+1){
return i;
}
else{
k-=tree[lc(i)].sz+1;
i=rc(i);
}
}
}
//以上为FHQ Treap
int root,x,y,z;
void Init(){
tot=0;
memset(tree,0,sizeof(tree));
root=0;
srand(19260817);
}
inline void Add(int num){
Split(root,num,x,y);
root=Merge(Merge(x,New(num)),y);
}
inline void Del(int num){
Split(root,num,x,z);
Split(x,num-1,x,y);
y=Merge(lc(y),rc(y));
root=Merge(Merge(x,y),z);
}
#define Get_K(rt,rk) tree[kth(rt,rk)].val
inline int Kth(int k){//获得数组中第k大
if (tree[root].sz<k) return -1;
return Get_K(root,tree[root].sz-k+1);
}
inline int Pre(int num){
Split(root,num-1,x,y);
int temp=Get_K(x,tree[x].sz);
root=Merge(x,y);
return temp;
}
inline int Delete_Pre(int num){
//删除全部小于num的数,直接删除左子树
Split(root,num-1,x,y);//x:左边
root=y;
return tree[x].sz;
}
};
using namespace FHQ_Treap;
#define INF 0x3f3f3f3f
inline char gc(){
char ch=getchar();
while (ch!='I'&&ch!='A'&&ch!='S'&&ch!='F') ch=getchar();
return ch;
}
int main(){
Init();
// Add(INF),Add(-INF);
int n=read(),Min=read();
int tag=0;//每个人的工资加上多少,类似于lazytag
int sum=0;
while (n--){
char opr=gc();
int num=read();
if (opr=='I'){
if (num<Min){continue;}//员工直接离开
Add(num-tag);
}
else if (opr=='A'){
tag+=num;//加工资的操作不会导致员工离开
}
else if (opr=='S'){
tag-=num;
sum+=Delete_Pre(Min-tag);
}
else if (opr=='F'){
int ans=Kth(num);
if (ans==-1) printf("-1\n");
else printf("%d\n",ans+tag);
}
}
printf("%d\n",sum);
}

 评论