块状链表
做一个平衡树的题。
看了题解突然发现可以用块状链表来搞。于是尝试了一下。
正好，借此题来说说块状链表。
（以下均为稍微明白了栋栋的所述的块状链表之后，自我的理解。）
原题：https://codevs.cn/problem/1286/
1286 郁闷的出纳员
题目描述 Description
OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。
好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？
输入描述 Input Description
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。
接下来的n行，每行表示一条命令。命令可以是以下四种之一：
_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。
在初始时，可以认为公司里一个员工也没有。
输出描述 Output Description
输出文件的行数为F命令的条数加一。
对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。
样例输入 Sample Input
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
样例输出 Sample Output
10
20
-1
2
数据范围及提示 Data Size & Hint
【约定】
l I命令的条数不超过100000
l A命令和S命令的总条数不超过100
l F命令的条数不超过100000
l 每次工资调整的调整量不超过1000
l 新员工的工资不超过100000
个人解法：
记得我们的分块吗？
分块大法好。
我们常常拿分块与莫队作比较，它们一个是在线，一个是离线。
我们也常常拿线段树与平衡树来作比较，它们一个是静态树，一个是动态树。
再回过来看，虽然分块比莫队强于“在线”，但是分块（与莫队）较之于平衡树还是弱于“插入”。
如果分块也可以动态维护，那么它与平衡树比起来就毫不逊色了。回想还有什么动态数据结构呢？对！链表。
我们知道，分块的核心在于平衡块的大小与块的个数。普通链表为什么不够快——因为块的个数很多（即O(n)），而块的大小很小（即O(1)）。于是我们采用分块，一个块记录sqrt(n)的信息，这样就平衡了。
动态维护
显然搞出这个东西来是为了支持动态维护的。插入很简单，插到对应的块就可以了。不过这样可能会使得一个块越来越大。于是我们设定一个阈值，比方说为sqrt(n)。当一个块的大小超过了阈值的2倍时，我们把这个块裂开。
这样就完成了动态维护。
复杂度与分块一样。只是稍微有了一个3左右的常数。
关于这个题
这个题，由于没有区间的限制，只是为了维护一个集合而已。所以我们可以规定链表顺序为从小到大的顺序。
之后操作就可以了。
（如果需要平衡树的题解，https://liaoy148.lofter.com/post/1da8a74e_d1a4ba4）
这样一来，我们就可以很方便地维护区间的动态问题了。有些时候这个东西（块状链表）比平衡树更好用。
举个例子：
有一个算法需要我们分块，每个块维护一个桶，这样是O(nsqrt(n))的空间复杂度。如果需要支持动态维护，怎么办？
在绞尽脑汁想平衡树套（七七八八的）树，还要压空间的时候，用个块状链表，就完成了。
以上题为例，代码如下：