fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define pb push_back
  4. using namespace std;
  5. const int N = 2e5;
  6.  
  7. struct wavelet {
  8. 	int lo, hi;
  9. 	wavelet *l, *r;
  10. 	vector<int> b;
  11.  
  12. 	wavelet(int *from, int *to, int x, int y) {
  13. 		lo = x, hi = y;
  14. 		if(lo == hi || from >= to)
  15. 			return;
  16. 		int m = (lo + hi) >> 1;
  17. 		auto f = [m](int x) {
  18. 			return x <= m;
  19. 		};
  20. 		b.reserve(to - from + 1);
  21. 		b.push_back(0);
  22. 		for(auto i = from; i != to; i++)
  23. 			b.push_back(b.back() + f(*i));
  24. 		auto pivot = stable_partition(from, to, f);
  25. 		l = new wavelet(from, pivot, lo, m);
  26. 		r = new wavelet(pivot, to, m + 1, hi);
  27. 	}
  28.  
  29. 	int kth(int l, int r, int k) {
  30. 		if(l > r) return 0;
  31. 		if(lo == hi) return lo;
  32. 		int in_left = b[r] - b[l - 1];
  33. 		int lb = b[l - 1];
  34. 		int rb = b[r];
  35. 		if(k <= in_left)
  36. 			return this->l->kth(lb + 1, rb, k);
  37. 		return this->r->kth(l - lb, r - rb, k - in_left);
  38. 	}
  39. 	//count of nos in [l, r] Less than or equal to k
  40. 	int LTE(int l, int r, int k) {
  41. 		if(l > r or k < lo) return 0;
  42. 		if(hi <= k) return r - l + 1;
  43. 		int lb = b[l-1], rb = b[r];
  44. 		return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
  45. 	}
  46.  
  47. 	//count of nos in [l, r] equal to k
  48. 	int count(int l, int r, int k) {
  49. 		if(l > r or k < lo or k > hi) return 0;
  50. 		if(lo == hi) return r - l + 1;
  51. 		int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
  52. 		if(k <= mid) return this->l->count(lb+1, rb, k);
  53. 		return this->r->count(l-lb, r-rb, k);
  54. 	}
  55. };
  56.  
  57. int Tc,n,a[N],k[N],j,q,l[N],r[N],ans[N];
  58. vector<int> v;
  59. map<int,int> mep;
  60.  
  61. int main()
  62. {
  63. 	int idx = 1;
  64. 	v.clear();
  65. 	mep.clear();
  66. 	scanf("%d %d",&n,&q);
  67. 	for(int i=0;i<n;i++){
  68. 		scanf("%d",&a[i+1]);
  69. 		v.push_back(a[i+1]);
  70. 	}
  71. 	for(int i=0;i<q;i++){
  72. 		scanf("%d %d %d",&l[i],&r[i],&k[i]);
  73. 	}
  74. 	sort(v.begin(), v.end());
  75. 	for(int i=0;i<v.size();i++){
  76. 		if(mep.find(v[i])==mep.end()) mep[v[i]] = idx, ans[idx++] = v[i];
  77. 	}
  78. 	for(int i=0;i<n;i++){
  79. 		a[i+1] = mep[a[i+1]];
  80. 	}
  81. 	wavelet T(a+1, a+n+1, 1, N);
  82. 	for(int i=0;i<q;i++){
  83. 		printf("%d\n", ans[T.kth(l[i], r[i], k[i])]);
  84. 	}
  85. 	return 0;
  86. } 
  87.  
  88.  
Success #stdin #stdout 0s 19152KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
5
6
3
https://ideone.com/BMZqj0
Wavelet Tree - http://w...content-available-to-author-only...j.com/problems/MKTHNUM/
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!