模拟小根堆

当堆大小超过 k 时，pop掉堆顶元素
堆顶元素就是第 k 大的数

#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl "\n"
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long long ll;
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------*/

int n,m;
int h[N],ind,cnt;

void down(int x){
   int t=x;
   if(2*x<=ind&&h[2*x]<h[t])t=2*x;
   if(2*x+1<=ind&&h[2*x+1]<h[t])t=2*x+1;
   if(t!=x){
   	swap(h[x],h[t]);
   	down(t);
   }
}
void up(int x){
   int t=x;
   if(x/2>=1&&h[x/2]>h[x])t=x/2;
   if(t!=x){
   	swap(h[x],h[t]);
   	up(t);
   }
}
void pop(){
   h[1]=h[ind];
   ind--;
   down(1);
}
void push(int x){
   h[++ind]=x;
   up(ind);
}
int main(){
   ioio
   cin>>n>>m;
   string op;
   int x;
   while(n--){
   	cin>>op;
   	if(op=="I"){
   		cin>>x;
   		push(x);
   		cnt++;
   		if(cnt>m)pop();
   	}
   	else {
   		cout<<h[1]<<endl;
   	}
   }
   return 0;
}