# POJ: K-th Number

`7 31 5 2 6 3 7 42 5 34 4 11 7 3`
`563`
`#include <cstdio>#include <vector>#include <algorithm>using namespace std;#define B 707int n, m;int main(int argc, char* argv[]) {  scanf("%d%d", &n, &m);  vector<int> data(n);  vector<int> sorted(n);  int bucket_num = (n + B - 1) / B;  vector<vector<int> > buckets(bucket_num, vector<int>(B));  if (n % B != 0) buckets[bucket_num - 1].resize(n % B);  getchar();  for (int i = 0; i < n; ++i) {    scanf("%d", &data[i]);    sorted[i] = data[i];    buckets[i / B][i % B] = data[i];  }  sort(sorted.begin(), sorted.end());  for (int i = 0; i < bucket_num; ++i) sort(buckets[i].begin(),     buckets[i].end());  while (m--) {    int i, j, k;    getchar();    scanf("%d%d%d", &i, &j, &k);    int start = -1;    int end = n - 1;    while (end > start + 1) {      int middle = start + (end - start) / 2;      int value = sorted[middle];      int c = 0;      int left = i - 1;      int right = j;            while (left < right && (left % B != 0))        if (data[left++] <= value) ++c;      while (left < right && (right % B != 0))        if (data[--right] <= value) ++c;            while (left < right) {        c += upper_bound(buckets[left / B].begin(), buckets[left / B].end(), value) - buckets[left / B].begin();        left += B;      }      if (c >= k) end = middle;      else start = middle;    }    printf("%d\n", sorted[end]);  }  return 0;}`

--

--