Участник:Novruzov.sb/K-th Number

Ссылки сюда (2) →

https://www.spoj.com/problems/MKTHNUM

C++

#include <cstdio>
 
static int A[100010], B[100010], *st[500000], val;
static int N, M, K, qs, qe, idx; int *P[100010];
 
void merge(int i, int j, int m, int n){
    int *p=new int[j-i+2];
    int k=m+1, l=i, q=i, s=i;
    while (i<=m && k<=j)
        B[l++]=(A[i]<A[k])? A[i++]: A[k++];
    while (k<=j) B[l++]=A[k++];
    while (i<=m) B[l++]=A[i++];
    for (;q<=j; q++) A[q]=p[q-s+1]=B[q];
    p[0]=j-s+1; st[n]=p;
}
void mergesort(int i, int j, int n){
    if (i < j){
       int m=(i+j)/2;
       mergesort(i, m, 2*n+1);
       mergesort(m+1, j, 2*n+2);
       merge(i, j, m, n);
    }
    else if(i==j){
        int *p=new int[2];
        p[0]=1; p[1]=A[i]; st[n]=p;
    }
}
inline void query(int x, int y, int n){
    if(y<qs || qe<x) return;
    if(qs<=x && y<=qe){P[++idx]=st[n]; return;}
    int m=(x+y)>>1;
    query(x, m, 2*n+1); query(m+1, y, 2*n+2);
}
 
int main()
{
    scanf("%d %d", &N, &M); int ans, p, q;
    for(int i=1; i<=N; ++i) scanf("%d", &A[i]);
    mergesort(1, N, 1);
    while(M--){
        scanf("%d %d %d", &qs, &qe, &K);
        idx=0; query(1, N, 1);
        for (int i=1; i<=idx; ++i){
            p=1, q=P[i][0];
            while(p<=q){
                int mid=(p+q)>>1; val=P[i][mid]; ans=0;
                for(int j=1; j<=idx; ++j){
                    int s=1, e=P[j][0];
                    while(s<=e){
                        int m=(s+e)>>1;
                        if(val<=P[j][m]) e=m-1;
                        else s=m+1;
                    }
                    ans+=s-1;
                }
                if (ans+1==K) break;
                if(ans+1>K)q=mid-1;
                else p=mid+1;
            }
            if(ans+1==K){printf("%d\n", val); break;}
        }
    }
    return 0;
}