本文不想废话，直接上多种做法。

题意：固定的k，动态加点，动态询问第k大数。

一、树状数组+二分

这里有两种做法，一种是二分sum(i)，另一种是利用二进制二分逼近k。

树状数组常用来处理区间点的统计情况，这里n没有规定大小（理论上是int32），但是操作次数n是小于1000,000的，所以可以先进行离散化来储存1000,000个点值（我不知道这是不是所谓的离散化，因为点本身是整数，但是，这至少是一种散列、一种映射，异曲同工的）。

具体操作为，先读入样例中出现的所有点，然后排序，insert( lower_bound(list, list+n, a[i])-list+1 ) 。a[]为原始数列，list为排序后数列，+1为了避免下标为0。至此便完成了离散化。

返回第k大数：

① 二分sum(i)，利用二分查找的思想，目标为 tot-sum(ans) < k <= tot-sum(ans-1)。sum()为树状数组的求和操作。要注意的是，树状数组中c[x]记录的是x的权值，也就是有c[x]个数同为x，则在查找第k大数的时候不一定是正好的，不能按原始的二分查找的模式，这里WA了好多次......

② 二进制二分逼近，本来是受以下二者启发，

http://tieba.baidu.com/f?kz=1033300126

http://www.cnblogs.com/zgmf_x20a/archive/2008/11/15/1334109.html

用来求第k小数的，显然已知总点数的情况下可以用来求得第k大数。

但是后来发现第一种的版本是错的，

代码类似

int ans=0;	for(int i=1<
     
      >=1)	{		if(c[ans+i] <= k)		{			k-=c[ans+=i];		}	}	return ans;
     

我因为这个WA了好久，有两个错误，①改成 if(c[ans+i] < k)，最后return ans+1。理由同上面红字。 ② if 中还要加上 ans+i<all &&...

代码（两种方法合在一起，见注释）：

//hdoj-4006，动态求第k大数#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MAXN 1000005#define LOWBIT(x) x&(-x)int a[MAXN];		//原数组，最多1000000个数int list[MAXN];	//排序数列int q[MAXN];		//是否询问：Qint c[MAXN];int n, k, all;int log2(int x) { int i=0; for(; x; x>>=1, i++); return i-1; }void insert(int x){	while(x<=all)	{		c[x]+=1;		x+=LOWBIT(x);	}}/// 方法一：二进制，二分逼近int find_kth_small(int k){	int ans=0;	for(int i=1<
         
          >=1)	{		if(ans+i
          
           >=1) { ans+=i; if(ans>=all || cnt+c[ans]>=k) ans-=i; else cnt+=c[ans]; } return ans+1; */}int find_kth_great(int k, int tot){ return find_kth_small(tot-k+1);}/// 方法二：二分sum(i)int sum(int i){ int res=0; for(; i>0; i-=LOWBIT(i)) { res+=c[i]; } return res;}int search(int k) //!!目标是 tot-sum(ans) < k <= tot-sum(ans-1)，而普通的二分查找目标是k=a[ans].{ int l=1, r=all; int tot = sum(r); while(l<=r) { int mid = (l+r)/2; if(tot-sum(mid)>=k) { l = mid+1; } else if(tot-sum(mid)
           
            =k) l=mid+1; else r = mid-1; } return l-1; */}int main(){ while(cin>>n>>k) { memset(c, 0, sizeof(c)); memset(q, 0, sizeof(q)); all = 0; //记录总共加入的数 for(int i=0; i
            
             >t; if(t[0] == 'I') { int x; cin>>x; a[i] = x; //a[] 原数列 list[all++] = x; //加入的数列，之后要经过排序，方便散列 } else if(t[0] == 'Q') { q[i] = 1; } } sort(list, list+all); int tot=0; for(int i=0; i
            
           
          
         
        
       
      
     

二、建堆

做一个小顶堆，放k个元素。每insert一个数，如果此数大于堆顶，就插入堆，并去掉原堆顶，如果小于则不操作，因为无影响。这个就是利用了这个题目的特殊性，即一个样例中k是固定不变的，不像其他题目可能会输入"Q k"这样作为一条指令。也因此造就了本场比赛第一水题。（掩面.....）

众所周知，优先队列（priority_queue）是用二叉堆实现的，下面给出STL优先队列的版本：

#include
     
      #include
      
       #include
       
        using namespace std;struct cmp{	bool operator() (int a, int b) {return a