0%

题解-LG1486

发表于 更新于 分类于
SBT解题，基本涵盖了所有SBT可以实现的功能，算是模板了吧

利用最近学的数据结构SBT过了此题，故来讲讲节点大小平衡树的做法。[戳我了解Size-Balanced-Tree]

这道题考察了大部分平衡树的操作，如插入、删除、查第k大元素等，所以可以视为弱化版的模板。

此题特别的一点就是要用一个变量统计一下所有成员的工资，一个比较妙的操作是：在员工加入后直接存储他与最低工资的差值即可

简析一下四种操作怎么处理：

1
2
3
4
5
6
7
1.插入权值为k-min的结点

2.把SBT上所有结点的值加k

3.把SBT上所有结点的值减k，减完后把低于min的结点删除。

4.查询SBT第k大，可以转化为SBT第(siz-k)小。如果范围越树尺寸输出-1就好。

最后，请注意一个坑点：在加入新成员的时候，要注意如果他一来就不符合条件，就直接劝退不insert即可。

此处未对SBT进行封装，简洁明了，便于理解。

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;

int read()
{
	int num=0;
	int flg=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')
		{
			flg=-1;
		}
		c=getchar();
	}
	while(isdigit(c))
	{
		num=(num<<1)+(num<<3)+(c^48);
		c=getchar();
	}
	return num*flg;
}

const int maxn=1e6+7;

#define ls(x) (t[x].l)
#define rs(x) (t[x].r)
struct SBT
{
	int val;
	int l;
	int r;
	int siz;
} t[maxn];

int rt=0;
int cnt=0;

void lrot(int &x)
{
	int y=rs(x);
	rs(x)=ls(y);
	ls(y)=x;
	t[y].siz=t[x].siz;
	t[x].siz=t[ls(x)].siz+t[rs(x)].siz+1;
	x=y;
}

void rrot(int &x)
{
	int y=ls(x);
	ls(x)=rs(y);
	rs(y)=x;
	t[y].siz=t[x].siz;
	t[x].siz=t[ls(x)].siz+t[rs(x)].siz+1;
	x=y;
}

void maintain(int &x,bool lr)
{
	if(!lr)
	{
		if(t[ls(ls(x))].siz>t[rs(x)].siz)
		{
			rrot(x);
		}
		else if(t[rs(ls(x))].siz>t[rs(x)].siz)
		{
			lrot(ls(x));
			rrot(x);
		}
		else
		{
			return ;
		}
	}
	else
	{
		if(t[rs(rs(x))].siz>t[ls(x)].siz)
		{
			lrot(x);
		}
		else if(t[ls(rs(x))].siz>t[ls(x)].siz)
		{
			rrot(rs(x));
			lrot(x);
		}
		else
		{
			return ;
		}
	}
	maintain(ls(x),0);
	maintain(rs(x),1);
	maintain(x,1);
	maintain(x,0);
}

void insert(int &x,int val)
{
	if(!x)
	{
		x=++cnt;
		t[x].val=val;
		t[x].siz=1;
		return ;
	}
	t[x].siz++;
	if(val<t[x].val)
	{
		insert(ls(x),val);
	}
	else
	{
		insert(rs(x),val);
	}
	maintain(x,val>=t[x].val);
}

int del(int &x,int val)
{
	t[x].siz--;
	int res=0;
	if(val==t[x].val||(val<t[x].val&&!ls(x))||(val>t[x].val&&!rs(x)))
	{
		res=t[x].val;
		if(!ls(x)||!rs(x))
		{
			x=ls(x)+rs(x);
		}
		else
		{
			t[x].val=del(ls(x),t[x].val+1);
		}
		return res;
	}
	if(val<t[x].val)
	{
		res=del(ls(x),val);
	}
	else
	{
		res=del(rs(x),val);
	}
	return res;
}

int kth(int &x,int val)
{
	if(val==t[ls(x)].siz+1)
	{
		return t[x].val;
	}
	else if(val<=t[ls(x)].siz)
	{
		return kth(ls(x),val);
	}
	else
	{
		return kth(rs(x),val-t[ls(x)].siz-1);
	}
}

int main()
{
	int n=read();
	int lim=read();
	int ans=0;
	int tot=0;
	int add=0;
	rt=0;
	int tt=0;
	t[0].siz=0;
	for(ri i=1; i<=n; i++)
	{
		string s;
		cin>>s;
		int k=read();
		if(s[0]=='I'&&k>=lim)
		{
			insert(rt,k-add);
			++tot;
		}
		if(s[0]=='A')
		{
			add+=k;
		}
		if(s[0]=='S')
		{
			int j;
			add-=k;
			while(tot&&(j=kth(rt,1))+add<lim)
			{
				del(rt,j);
				--tot;
				++ans;
			}
		}
		if(s[0]=='F')
		{
			if(k>tot)
			{
				puts("-1");
			}
			else
			{
				printf("%d\n",kth(rt,tot-k+1)+add);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}