实现kth_element

快排的思想，选定一个基准数，将大于 $mid$ 的数放到右边，小于的放到左边，然后比较 $mid$ 和 $k$ 的位置，递归重复操作即可。

#pragma GCC optimize("Ofast")
#include <cstdio>

inline int read() {
<!--more--> 
  int x = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w ^= 1;
    c = getchar();
  }
  while (c <= '9' && c >= '0') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return w & 1 ? x : -x;
}

int kth_element(int* a, int l, int r, int k) {
  int mid = l - 1;
  for (int i = l; i < r; ++i) {
    if (a[i] < a[r] && a[i] ^ a[++mid]) a[i] ^= a[mid] ^= a[i] ^= a[mid];
  }
  if (a[++mid] ^ a[r]) a[mid] ^= a[r] ^= a[mid] ^= a[r];
  if (mid == k) return a[mid];
  return (mid >= k) ? kth_element(a, l, mid - 1, k)
                    : kth_element(a, mid + 1, r, k);
}

int a[2000006];

int main() {
  int n, k;
  n = read();
  k = read();
  for (int i = 0; i < n; ++i) a[i] = read();
  // random_shuffle(a, a + n);
  printf("%d\n", kth_element(a, 0, n - 1, n - k));
  return 0;
}