这里提供一个简单实现新思路：

.

约定：

1. 以下n指代的数的数量，不是题目所指的n
2. 以下m指代询问的数量，不是题目所指的m

（不好意思，这是本人习惯）

分块+堆

**堆一次只能输出堆顶的一个元素，如果我要找第k小的元素， 理论上复杂度是 O（k*n）,这样肯定会TLE**

那么我们能不能，把这些数排序后分成几段连续的数在几个堆里,没次查找先去找在哪个堆，再去找在堆里的排名

这样做的话，就可以跳过一些数了

那分成几段才比较优？

分少了，堆里查找就会慢

分多了，找堆就会慢

如果你学过分块的话，你就可以反应过来了,分成根号n段理论上是最好的，因为平摊了两个步骤的复杂度

查找的时候通过 O(sqrt n)来找到在哪个堆，再用 O(sqrt n* log n)在堆里来找到它的具体数值

插入值与查找类似，先找到所处的堆，再加入到堆

还有细节问题，请看代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
const int N=3e5+10,M=N;
int A[N],B[N],belong[N];
priority_queue<int>q[M];
int m,n;
inline void add(int x){
    int op=lower_bound(B+1,B+1+m,x)-B;
    int blo=belong[op];
    q[blo].push(-x);
}
int size,all;
inline int ask(int x){
    int op;
    for(int i=0;i<=m;i++){
        if(x>q[i].size())
        x-=q[i].size();
        else{
            op=i;
            break;
        }
    }
    vector<int>p;
    int ans=0;
    while(q[op].size()){
        int u=-q[op].top();q[op].pop();
        //弹出
        p.push_back(u);
        x--;
        if(x==0){
            ans=u;
            break;
        }
    }
    for(int i=0;i<p.size();i++)
    q[op].push(-p[i]);//把弹出的数再放回去
                             
    return ans;
}
signed main(){
    cin>>m>>n;
    size=pow(m,1.0/3.0);
    all=ceil((double)m/size);
    for(int j=1;j<=all;j++)
    for(int i=(j-1)*size+1;i<=j*size;i++)
    belong[i]=j;
    //初始化块
    for(int i=1;i<=m;i++){
        scanf("%lld",&A[i]);
        B[i]=A[i];
    }
    sort(B+1,B+1+m);
   //排序方便判断排名，选择堆
    int num=1;
    for(int i=1,x;i<=n;i++){
        scanf("%lld",&x);
        for(int j=num;j<=x;j++)add(A[j]);
        num=x+1;
        printf("%lld\n",ask(i));
    }
}

题解 P1801 【黑匣子_NOI导刊2010提高（06）】

原文：https://www.cnblogs.com/naruto-mzx/p/11605924.html