建议加强数据

rt，我随便捣鼓出来的 O(n\log \sqrt{n}) 排序水过去了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5,B=1e4+5;
int a[N],L[B],R[B],now[B];
vector<int>block[B],ans;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    int t=sqrt(n);
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=t;++i)
    {
        L[i]=R[i-1]+1;
        R[i]=R[i-1]+t;
    }
    if(R[t]<n)
    {
        ++t;
        L[t]=R[t-1]+1;
        R[t]=n;
    }
    for(int i=1;i<=t;++i)
    {
        for(int j=L[i];j<=R[i];++j)
            block[i].push_back(a[j]);
        sort(block[i].begin(),block[i].end());
    }
    for(int i=1;i<=t;++i)
        q.emplace(block[i][0],i);
    while(!q.empty())
    {
        int x=q.top().first,y=q.top().second;
        q.pop();
        ++now[y];
        ans.emplace_back(x);
        if(now[y]<block[y].size())q.emplace(block[y][now[y]],y);
    }
    cout<<ans[k];
}