To find the K-th largest number, we often think of the chairman tree, but the chairman tree code is complex and the operation is complex. If we simply find the K-th-largest number in the sequence, then it seems to have advantages and disadvantages, like ACdream 1099 This problem is to find the number with the largest K in the sequence, and if there is any repetition, it will be included in the K, for example: if the sequence is {3, 2, 2, 1}, the number with the largest number is obviously 3, and the number with the second largest number is obviously 2, which is no doubt, but is the number with the third largest 1 or 2? For this problem, the third is 2, and the fourth is 1
Seeing this problem, many people will directly think of sort, and then find the K-th number. But sort is tle's. In fact, he studies the idea of divide and rule, and writes a sorting rule himself, but needs some optimization
First of all, read the divide and conquer, sort and optimize the code

//Find the number K in the sequence
int sort_up_kth(int left,int right,int n,int k)
{//Left and right are left and right interval boundaries respectively, n is sequence length
    int l=left;
    int r=right;
    //You don't use left and right to perform the operation directly because the next processing time
    //These two values may be modified, but they may be used in the end
    //Therefore, only two variables can be defined to modify their assignment
    if(l<r){//Meet the requirements
       int x=a[l];
       while(l<r){
        while(l<r&&a[r]<x) r--;
        //Find the first number greater than or equal to the current value from the right endpoint to the left
        if(l<r) {
            a[l]=a[r];
            l++;
        }
        while(l<r&&a[l]>=x) l++;
        //Find the first number less than the current value from the left to the right
        if(l<r) {
            a[r]=a[l];
            r--;
        }
       }
       a[l]=x;
       if(l==k) return 1;//Find the number K, end it directly, save time
       if(l>k) sort_up_kth(left,l-1,n,k);
       //Divide and rule thought
       else sort_up_kth(l+1,right,n,k);
    }
}
//In fact, in this sequence, only the first K numbers are arranged, and the other numbers are in disorder

This is how to solve the K-th-largest number in the sequence. Simply understand the principle (what I wrote is not detailed, please forgive me), and then you can easily derive the solution of the K-th-smallest number

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int a[5000005];
int sort_up_kth(int left,int right,int n,int k)
{//Number K
    int l=left;
    int r=right;
    if(l<r){
       int x=a[l];
       while(l<r){
        while(l<r&&a[r]<x) r--;
        if(l<r) {
            a[l]=a[r];
            l++;
        }
        while(l<r&&a[l]>=x) l++;
        if(l<r) {
            a[r]=a[l];
            r--;
        }
       }
       a[l]=x;
       if(l==k) return 1;
       if(l>k) sort_up_kth(left,l-1,n,k);
       else sort_up_kth(l+1,right,n,k);
    }
}
int sort_down_kth(int left,int right,int n,int k)
{//K-th small number
    int l=left;
    int r=right;
    if(l<r){
        int x=a[l];
        while(l<r){
            while(l<r&&a[r]>x) r--;
            if(l<r){
                a[l]=a[r];
                l++;
            }
            while(l<r&&a[l]<=x) l++;
            if(l<r){
                a[r]=a[l];
                r--;
            }
        }
        a[l]=x;
        if(l==k) return 1;
        if(l>k) sort_down_kth(left,l-1,n,k);
        else sort_down_kth(l+1,right,n,k);
    }
}
int main(){
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort_up_kth(1,n,n,k);
        printf("The first%d The big numbers are%d\n",k,a[k]);
        sort_down_kth(1,n,n,k);
        printf("The first%d The small number is%d\n",k,a[k]);
    }
return 0;}
///6 3
///1 2 3 4 5 6
///The number three is four
///The third small number is three
///6 4
///1 2 3 4 4 4
///The number four is three
///The fourth small number is four
///6 4
///1 3 2 1 2 3
///The number four is two
///The fourth small number is two

I have limited ability. If there is any mistake, please correct it