专题扩展(1) - 分块思想

来看一个问题: 给出一个非负整数序列A[]，元素个数为N ($N<=10^5, A[i]<=10^5$) 在有可能随时添加或删除元素的情况下，实时查询序列元素第K大，即把序列元素从小到大排序后从左到右的第K个元素。例如对序列 2,7,5,1,6 来说，此时序列第3大为5; 之后插入元素4,这样序列第3大就是4; 然后删除元素1, 于是序列第1大就是2。一般来说，如果在查询的过程中元素可能发生改变(例如插入、修改或删除)，就称这种查询为在线查询; 如果在查询过程中元素不发生改变，就称为离线查询。事实上，序列元素第K大有很多解决方法，本节将介绍其中较容易理解、写法也很简洁的一种做法，即分块的思想。

一般来说为了达到高效率的目的，对一个有N个元素的有序序列来说，除最后一块外，其余每块中元素的个数都应当为 low(sqrt(N)) (此处为向下取整)，于是块数为 high(sqrt(N)) (此处为向上取整)。这样就把有序序列划分为 high(sqrt(N)) 块，其中每块中元素的个数不超过 low(sqrt(N))。例如对有11个元素的序列来说，就应当分为 high(sqrt(11))=4 块，其中每块中的元素个数分别为 3、3、3、2。

题解: 设置一个hash 数组 table[100001]，其中 table[x] 表示整数X的当前存在个数: 接着，借助分块思想，将100001分为317块，其中每块的元素个数为316。同时，这样分块有什么用呢?可以定义一个统计数组 block[317]，其中 block[i] 表示第i块中存在的元素个数。于是假如要新增一个元素 x，就可以先计算出x 所在的块号为 x/316，然后让block[x/316]加1，表示该块中元素个数多了1; 同时table[x]加1，表示整数x的当前存在个数多了1。整体思路是先用O(√N)的时间复杂度找到第K大的元素在哪一块，然后再用O(√N)的时间复杂度在块内找到这个元素，因此单次询的总时间复杂度为0(√N)

例题1. Stack

Stack is one of the most fundamental data structures, which is based on the principle of Last InFirst Out (LIFO). The basic operations include Push (inserting an element onto the top position) andPop (deleting the top element). Now you are supposed to implement a stack with an extra operation:PeekMedian–return the median value of all the elements in the stack. With N elements, the medianvalue is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th ifN is odd

input: Each input file contains one test case. For each case, the first line contains a positive integer N($<10^5$). Then N lines follow, each contains a command in one of the following 3 formats: Push key Pop PeekMedian where key is a positive integer no more than $10^5$.

output: For each Push command, insert key into the stack and output nothing. For each Pop orPeekMedian command, print in a line the corresponding returned value. If the command is invalid, print “Invalid” instead.

eg:

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

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