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