Saikr Online Judge 点名

使用堆的解法

对于求第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;
}