算法分析

• 向这样的动态求第k小的值，并且k的变化要么+1 要么-1 要么不变的话，就可以用对顶堆数据结构。存储形式如下
  大根堆 小根堆
  ---------> <-------
  从左到右数值是递增的

• 如图小根堆的对顶就是每次的答案。

• 具体操作
  • 当加入一个数x的话判断如果大根堆为空或者x >= 小根堆堆顶的话直接加入小根堆中
  • 反之加入到大根堆中，并且把大根堆堆顶的数添加到小根堆中，并把大根堆堆顶删除
  • 当来到一次get操作
    while(j < m &&　get[j] == i) { cout << up.top() << end; down.push(up.top()); up.pop(); }