fork(13) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 100005;
  5. const int LIM = 263005;
  6.  
  7. #define inchar getchar_unlocked
  8. #define outchar(x) putchar_unlocked(x)
  9.  
  10. template<typename T> void inpos(T &x){x=0;register T c=inchar();while(((c<48)||(c>57))&&(c!='-'))c=inchar();bool neg=false;if(c=='-')neg=true;for(;c<48||c>57;c=inchar());for(;c>47&&c<58;c=inchar())x=(x<<3)+(x<<1)+(c&15);if(neg)x=-x;}
  11. template<typename T> void outpos(T n){if(n<0){outchar('-');n*=-1;}char snum[65];int i=0;do {snum[i++]=n%10+'0';n/=10;}while(n);i=i-1;while(i>=0)outchar(snum[i--]);outchar('\n');}
  12.  
  13. int inp[MAX];
  14. vector< pair<int,int> > nums;
  15. vector<int> seg[LIM];
  16.  
  17. void build_merge_sort(int t, int i, int j) {
  18. if (i==j) {
  19. seg[t].push_back(nums[i].second);
  20. return ;
  21. }
  22. int left = t<<1, right = left|1, mid = (i+j)/2;
  23. build_merge_sort(left, i, mid);
  24. build_merge_sort(right, mid+1, j);
  25. merge(seg[left].begin(), seg[left].end(), seg[right].begin(), seg[right].end(), back_inserter(seg[t]));
  26. }
  27.  
  28. int query_kth(int t, int i, int j, int l, int r, int k) {
  29. if (i == j) {
  30. return seg[t][0];
  31. }
  32. int left = t<<1, right = left|1, mid = (i+j)/2, total;
  33. auto it = upper_bound(seg[left].begin(), seg[left].end(), r);
  34. total = it - lower_bound(seg[left].begin(), seg[left].end(), l);
  35. if (total >= k) {
  36. return query_kth(left, i, mid, l, r, k);
  37. }
  38. else {
  39. return query_kth(right, mid+1, j, l, r, k-total);
  40. }
  41. }
  42.  
  43. int main() {
  44. int n, m, x, y, k, idx, ans;
  45. inpos(n), inpos(m);
  46. for(int i=0; i<n; ++i) {
  47. inpos(x);
  48. inp[i] = x;
  49. nums.push_back(make_pair(x, i));
  50. }
  51. sort(nums.begin(), nums.end());
  52. build_merge_sort(1, 0, n-1);
  53. while (m--) {
  54. inpos(x), inpos(y), inpos(k);
  55. --x; --y;
  56. idx = query_kth(1, 0, n-1, x, y, k);
  57. ans = inp[idx];
  58. outpos(ans);
  59. }
  60. return 0;
  61. }
Success #stdin #stdout 0s 21784KB
stdin
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
5
6
3