C++ 代码

#include<bits/stdc++.h>
using namespace std;
vector<int > v;
const int N=30000;
int a[N];
struct {
    int l,r,s;
}hjt[N*40];
int root[N],cnt=0;
void update(int pre,int &now,int l,int r,int pos){
    now=++cnt;
    hjt[now]=hjt[pre];
    ++hjt[now].s;
    if(l==r){ return ;
    }
    int m=(l+r)>>1;
    if(pos<=m) update(hjt[pre].l,hjt[now].l,l,m,pos);
    else if(pos>m)update(hjt[pre].r,hjt[now].r,m+1,r,pos);
}
int query(int pre,int now,int l,int r,int k){
    if(l==r) return l;
    int num=hjt[hjt[now].l].s-hjt[hjt[pre].l].s;
    int m=(l+r)>>1;
    if(k<=num) return query(hjt[pre].l,hjt[now].l,l,m,k);
    else if(num<k) return query(hjt[pre].r,hjt[now].r,m+1,r,k-num);
}
int LB(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int u[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        v.push_back(a[i]);
    }
    for(int i=1;i<=m;++i)
        scanf("%d",&u[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int vs=v.size();
    root[0]=0;
    for(int i=1;i<=n;++i){
        update(root[i-1],root[i],1,vs,LB(a[i]));
    }
    int l,r=0,k=0,j=1;
    while(j<=m){
        if(r<n)
            l=1,r++;
        if(r==u[j]) {
            k++;
            printf("%d\n",v[ query(root[l-1],root[r],1,vs,k)-1]);
            j++;
            r--;
        }
    }
    return 0;
}