分块思想

　　给出一个非负整数序列A，元素个数为N(N≤10⁵,A[i]≤10⁵)，在有可能随时添加或删除原数的情况下，实时查询序列元素第K大，即把序列元素从小到大排序后从左到右的第K个元素。例如对序列{2,7,5,1,6}来说，此时序列第3大为5；之后插入元素4，这样序列第3大就是4；然后删除元素，于是序列第1大就是2.
如果在查询的过程中元素可能发生改变（例如插入、修改或删除），就称这种查询为在线查询；如果在查询过程中元素不发生改变，就称为离线查询。显然，上面的序列元素第K大的问题是在线查询，如果直接暴力做，在添加跟删除元素时就要有O(n)的时间复杂度来移动序列的元素，效率极其低下。事实上，序列元素第K大有很多解决方法，介绍其中较容易理解、写法也很简洁的一种做法，即分块的思想。

分块思想
　　从字面意思理解“分块”，就是把有序元素划分为若干块。例如，可以把拥有9个元素的有序序列{1,2,4,9,12,34,56,78,87}分为3块{1,2,4}、{9,12,34}、{56,78,87}。为了达到高效率的目的，对一个有N个元素的有序序列来说，除最后一块外，其余每块中元素的个数都应当为floor(sqrt(N))，于是块数为ceil(sqrt(N))。这样就把有序序列划分为ceil(sqrt(N))块，其中每块中元素的个数不超过floor(sqrt(N))。例如对有9个元素的序列来说，就应当分为sqrt(9)=3块，其中每块中的元素个数为别为3、3、3；而对有11个元素的序列来说，就应当分为ceil(sqrt(11))=4块，其中每块中的元素个数分别为3、3、3、2。

　　暴力的做法由于添加和删除元素时需要O(n)的复杂度来移动元素，那么如何用分快法降低这个时间呢？考虑到序列中的元素都是不超过10⁵的非负整数，因此不妨设置一个hash数组table数组table[100001]，其中table[x]表示整数x的当前存在个数；接着，借助分块思想，从逻辑上将0~10⁵分为ceil(√10⁵+1)=317块，其中每块的元素个数为floor(sqrt(10⁵+1))=316。逻辑上进行分块的结果如下：
0,1,2,……,314,315为第0块；
316,317,……,630,631为第1块。
……
99856,99857,……,100000为第316块。
　　定义一个统计数组block[317],其中block[i]表示第i块中存在的元素个数。于是加入要新增一个元素x，就可以先计算出x所在的块号为x / 316，然后让block[x/316]加1，表示该块中元素个数多了1；同时令table[x]加1，表示整数x的当前存在个数多了1。

　　例如想要新增334这个元素，就可以通过334/316=1算出元素334所在的块号为1，然后令block[1]++，表示1号块增加了一个元素，并令table[334]++，表示元素334的存在个数多了1.

　　同理，如果想要删除一个元素x，只需要让block[x/316]和table[x]都减1即可。显然，新增与删除元素的时间复杂度都是O(1)。

　　接着来看如何查询序列中第K大的元素是什么。

　　首先，从小到大枚举块号，利用block数组累加得到前i-1块中存在的元素总个数，然后判断加入i号块的元素个数后元素总个数能否达到K。如果能，则说明第K大的数就在当前枚举的这个块中，此时只需从小到大遍历该块中的每个元素（其中i号块的第一个元素时i*316），利用table数组继续累加元素的存在个数，指导总累计数达到K，则说明找到了序列第K大的数。显然整体思路是先用O(sqrt(N))的时间复杂度找到第K大的元素在哪一块，然后再用O(sqrt(N))的时间复杂的在块内找到这个元素，因此单次查询的总时间复杂度为O(sqrt(N))。

　　例如，令数据范围为0~8，那么就可以分为3块，其中0号块负责0~2,1号块负责3~5,2号块负责6~8.假设现在已经存在的元素为0,1,3,4,4,5,8，那么此时block数组与table数组的情况如下：

block[0]=2，表明0号块包含了2个元素；0,1

block[1]=4，表明1号块包含了4个元素；3,4,4,5

block[2]=1，表明2号块包含了1个元素；8

table[0]=table[1]=table[3]=table[5]=table[8]=1，表明它们各存在1个；

table[4]=2，表明元素4存在2个。

　　接下来查询当前序列{0,1,3,4,4,5,8}的第5大的数，即K=5。令sum表示当前已经累计存在的数的个数，初始为0。依次遍历每个块：

遍历到0号块时，sum+block[0]=0+1=2<5，因此第K大的数不在0号块，令sum=2。
遍历到1号块时，sum+block[1] = 2+4=6>5，因此第K大的数在1号块内。此时sum=2，接下来遍历1号块的每个元素，即3~5；

　　　　1）遍历到元素3时，计算sum=sum+table[3] =3<5，因此3不是第K大的数。

　　　　2）遍历到元素4时，计算sum=sum+table[4] = 5>=5，因此4是第K大的数。

因此序列中第5大的数为4。

1057 Stack (30分)

　　堆栈是最基本的数据结构之一，它基于后进先出（LIFO）的原理。基本操作包括“推”（将元素插入到顶部位置）和“弹出”（删除顶部元素）。现在，您应该使用一个额外的操作来实现一个堆栈：PeekMedian-返回堆栈中所有元素的中值。用

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行都包含一个正整数

Push key
Pop
PeekMedian

其中key是正整数不大于 $1.$

输出规格：

对于每个Push命令，插入key到堆栈中，什么也不输出。对于每一个Pop或PeekMedian命令，则输出一条线对应的返回值。如果命令无效，请打印Invalid。

样本输入：

17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

样本输出：

Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

输入规格：

输出规格：

样本输入：

样本输出：

相关推荐