使用堆的解法
对于求第k大，相当于就是求容量为k的大根堆的堆顶元素，但是这里的k是[1...m],逐1增加。
假如现在大根堆的容量为k，要加入一些新元素过来，然后求第k+1大。
就可以将新元素插入大根堆，然后从大根堆取出堆顶再放入小根堆(因为此时的堆顶并不一定就是第k+1大)，这里的作用就是看哪些新元素能够直接留在容量k的大根堆，然后把一些不属于大根堆的元素踢出来，放入小根堆。
然后要求第K+1大的时候，就再把小根堆的堆顶放入到大根堆。现在就变成了容量为K+1的大根堆，堆顶就是答案了。
代码
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class T> void pt(T x){
cout<<x<<" ";
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout<<t<<" ";
pt(data...);
}
//--------------------------------------------
int N,M;
ll a[maxn],b[maxn];
priority_queue<ll,vector<ll>,greater<ll> > qmin;
priority_queue<ll> qmax;
int main(){
// debug_in;
read(N,M);
for(int i = 1;i<=N;i++) read(a[i]);
for(int i = 1;i<=M;i++) read(b[i]);
for(int i = 1;i<=M;i++){
for(int j = b[i-1] + 1;j<=b[i];j++){
qmax.push(a[j]);
qmin.push(qmax.top());
qmax.pop();
}
qmax.push(qmin.top());qmin.pop();
printf("%lld\n",qmax.top());
}
return 0;
}平衡树做法
对于平衡树来说，就是板子题了，只不过代码量太大。
这里使用的是treap平衡树
代码
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll maxM = 1e6+10;
const ll inf = 1e17;
const ll inf2 = 1e17;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template<class T> void pt(T x){
cout<<x<<" ";
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout<<t<<" ";
pt(data...);
}
//--------------------------------------------
struct Treap{
ll root,idx;
struct node{
ll l,r;
ll key,val;
ll cnt,size;
}tr[100010];
void pushup(ll p){
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
ll get_node(ll key){
tr[++idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].size = 1;
return idx;
}
void zig(ll &p){
ll q = tr[p].l;
tr[p].l = tr[q].r,tr[q].r = p,p = q;
pushup(tr[p].r),pushup(p);
}
void zag(ll &p){
ll q = tr[p].r;
tr[p].r = tr[q].l,tr[q].l = p,p = q;
pushup(tr[p].l),pushup(p);
}
void build(){
get_node(-inf);get_node(inf);
root = 1,tr[1].r = 2;
pushup(root);
if(tr[1].val < tr[2].val) zag(root);
}
void insert(ll &p,ll key){
if(!p) p = get_node(key);
else if(tr[p].key == key) tr[p].cnt++;
else if(key < tr[p].key){
insert(tr[p].l,key);
if(tr[tr[p].l].val > tr[p].val) zig(p);
}else{
insert(tr[p].r,key);
if(tr[tr[p].r].val > tr[p].val) zag(p);
}
pushup(p);
}
void remove(ll &p,ll key){
if(!p) return ;
if(tr[p].key == key){
if(tr[p].cnt > 1) tr[p].cnt--;
else if(tr[p].l || tr[p].r){
if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val){
zig(p);
remove(tr[p].r,key);
}else{
zag(p);
remove(tr[p].l,key);
}
}else p = 0;
}else if(key < tr[p].key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
ll get_rank_by_key(ll p,ll key){
if(!p) return 0;
if(key < tr[p].key) return get_rank_by_key(tr[p].l,key);
else if(key == tr[p].key) return tr[tr[p].l].size + 1;
else return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r,key);
}
ll get_key_by_rank(ll p,ll rank){
if(!p) return inf;
if(rank <= tr[tr[p].l].size) return get_key_by_rank(tr[p].l,rank);
else if(rank <= tr[tr[p].l].size + tr[p].cnt) return tr[p].key;
else return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
ll get_prev(ll p,ll key){
if(!p) return -inf;
if(key <= tr[p].key) return get_prev(tr[p].l,key);
else return max(tr[p].key,get_prev(tr[p].r,key));
}
ll get_next(ll p,ll key){
if(!p) return inf;
if(key >= tr[p].key) return get_next(tr[p].r,key);
else return min(tr[p].key,get_next(tr[p].l,key));
}
}trp;
ll N,M;
ll a[maxn];
int main(){
// debug_in;
trp.build();
read(N,M);
ll last = 0,get = 1;
for(ll i = 1;i<=N;i++) read(a[i]);
for(ll i = 1;i<=M;i++){
ll t;read(t);
for(ll j = last+1;j<=t;j++){
trp.insert(trp.root,a[j]);
}
last = t;
ll ans = trp.get_key_by_rank(trp.root,get+1);
get++;
printf("%lld\n",ans);
}
return 0;
} 
京公网安备 11010502036488号