K优先队列——对顶堆（两种优先队列的组合）

题目描述
你需要维护一个队列，支持以下两种操作：
1.加入一个非负整数x；
2.取出当前队列中第k大的数字。
保证进行第二种操作时，队列中至少有k个数字。
部分数据经过加密，你需要依次处理每个操作才能获得正确的下一个操作。
输入
第一行包括三个非负整数n,k,p，分别表示操作次数，参数k以及数据是否进行过加密。
接下来n行，每行先给出一个数opt，表示操作类型。若opt=1,接下来还会有一个非负整数x,若p=0，表示往队列中加入x，若p=1，表示往队列中加入x异或上前一次出队操作取出的数字后得到的结果，如果还未进行过出队操作，把前一次取出的数字看作0。若opt=2，表示要求取出并输出当前队列中第k大的数字。
输出
对于每一个出队操作，输出一个正整数表示答案。
样例输入

样例输出

2
1

提示
对于100%的数据，1 ≤ k ≤ n ≤ 2∗10⁵ ，0 ≤ x ≤ 10⁹。

之前在upc也做过关于对顶堆的题，在洛谷还有这道题

对顶堆是由大根堆小根堆组成的一种数据结构，经常用来处理在线第 k 大（小），或者是动态中位数的问题
在这里插上一张图
图片来源：https://www.luogu.com.cn/user/119261
在这里插入图片描述
在这一道题目中适合上面放小根堆，下面放大根堆，小根堆里面的元素的顺序是从小到大排序的，大根堆里面的元素是从大到小排列的。小根堆的堆顶为小根堆中最小的元素，大根堆中的元素是大根堆中最大的元素。

利用这一特点，用上面的小根堆储存大的 k 个元素，其余的元素储存小的部分元素，这样一来，这两个堆也有单调性，即小根堆的堆顶（小根堆中最小的元素）大于大根堆的堆顶（大根堆中最大的元素），满足从上到下递减的关系，所以，每次小根堆的堆顶就是第 K 大的元素。

目标就是动态维护小根堆中尽量满足 K 个元素，不足时如果大根堆中还有元素，就将大根堆中的元素放入小根堆（运行错误在这里），意思就是说，如果大根堆中没有元素就没有办法pop()

code:

#include <bits/stdc++.h>
using namespace std;
#define wuyt main
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
    if(c == '-')Nig = -1,c = getchar();
    while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
    return Nig*x;}
#define read read()
const ll inf = 1e15;
const ll INF = 0x3f3f3f3f;
const int maxn = 3e5 + 7;
const int mod = 998244353;
#define pi 3.14159265358979323846
ll res,ans;
ll n,k,p;
priority_queue <ll ,vector<ll> ,greater<ll> > xiaogen;
priority_queue <ll ,vector<ll> ,less<ll> > dagen;
void in_it(ll x){
    if(xiaogen.size()<k) xiaogen.push(x);
    else{
        if(xiaogen.size()&&xiaogen.top()<x){
            dagen.push(xiaogen.top());
            xiaogen.pop();
            xiaogen.push(x);
        }
        else dagen.push(x);
    }
}
int main()
{
    n=read,k=read,p=read;
    ll temp=0;
    while(n--){
        ll opt=read;
        if(opt==1){
            ll x=read;
            if(p==0) in_it(x);
            else in_it(x^temp);
        }
        else{
            temp = xiaogen.top();
            printf("%lld
",temp);
            xiaogen.pop();
            if(dagen.size()){
                xiaogen.push(dagen.top());
                dagen.pop();
            }
        }
    }
    return 0;
}
/**
5 2 1
1 2
1 3
2
1 3
2
**/