fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x)	scanf("%d",&x)
  8. #define sl(x)	scanf("%lld",&x)
  9. #define ss(s)	scanf("%s",s)
  10. #define pi(x)	printf("%d\n",x)
  11. #define pl(x)	printf("%lld\n",x)
  12. #define ps(s)	printf("%s\n",s)
  13. #define deb(x) cout << #x << "=" << x << endl
  14. #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
  15. #define pb push_back
  16. #define mp make_pair
  17. #define F first
  18. #define S second
  19. #define all(x) x.begin(), x.end()
  20. #define clr(x) memset(x, 0, sizeof(x))
  21. #define sortall(x) sort(all(x))
  22. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  23. #define PI 3.1415926535897932384626
  24. typedef pair<int, int>	pii;
  25. typedef pair<ll, ll>	pl;
  26. typedef vector<int>		vi;
  27. typedef vector<ll>		vl;
  28. typedef vector<pii>		vpii;
  29. typedef vector<pl>		vpl;
  30. typedef vector<vi>		vvi;
  31. typedef vector<vl>		vvl;
  32. int mpow(int base, int exp); 
  33. void ipgraph(int m);
  34. void dfs(int u, int par);
  35. const int mod = 1000000007;
  36. const int N = 1e5, M = N;
  37. //=======================
  38. const int MAX = 1e6;
  39. vi g[N];
  40. int a[N];
  41. struct wavelet_tree{
  42. 	#define vi vector<int>
  43. 	#define pb push_back
  44. 	int lo, hi;
  45. 	wavelet_tree *l, *r;
  46. 	vi b;
  47.  
  48. 	//nos are in range [x,y]
  49. 	//array indices are [from, to)
  50. 	wavelet_tree(int *from, int *to, int x, int y){
  51. 		lo = x, hi = y;
  52. 		if(lo == hi or from >= to) return;
  53. 		int mid = (lo+hi)/2;
  54. 		auto f = [mid](int x){
  55. 			return x <= mid;
  56. 		};
  57. 		b.reserve(to-from+1);
  58. 		b.pb(0);
  59. 		for(auto it = from; it != to; it++)
  60. 			b.pb(b.back() + f(*it));
  61. 		//see how lambda function is used here	
  62. 		auto pivot = stable_partition(from, to, f);
  63. 		l = new wavelet_tree(from, pivot, lo, mid);
  64. 		r = new wavelet_tree(pivot, to, mid+1, hi);
  65. 	}
  66.  
  67. 	//kth smallest element in [l, r]
  68. 	int kth(int l, int r, int k){
  69. 		if(l > r) return 0;
  70. 		if(lo == hi) return lo;
  71. 		int inLeft = b[r] - b[l-1];
  72. 		int lb = b[l-1]; //amt of nos in first (l-1) nos that go in left 
  73. 		int rb = b[r]; //amt of nos in first (r) nos that go in left
  74. 		if(k <= inLeft) return this->l->kth(lb+1, rb , k);
  75. 		return this->r->kth(l-lb, r-rb, k-inLeft);
  76. 	}
  77.  
  78. 	//count of nos in [l, r] Less than or equal to k
  79. 	int LTE(int l, int r, int k) {
  80. 		if(l > r or k < lo) return 0;
  81. 		if(hi <= k) return r - l + 1;
  82. 		int lb = b[l-1], rb = b[r];
  83. 		return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
  84. 	}
  85.  
  86. 	//count of nos in [l, r] equal to k
  87. 	int count(int l, int r, int k) {
  88. 		if(l > r or k < lo or k > hi) return 0;
  89. 		if(lo == hi) return r - l + 1;
  90. 		int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
  91. 		if(k <= mid) return this->l->count(lb+1, rb, k);
  92. 		return this->r->count(l-lb, r-rb, k);
  93. 	}
  94. 	~wavelet_tree(){
  95. 		// if(l!=NULL) cout<<(l->lo)<<" "<<(l->hi)<<endl;
  96. 		// if(r!=NULL) cout<<(r->lo)<<" "<<(r->hi)<<endl;
  97. 		// if(l!=NULL) delete l;
  98. 		// if(r!=NULL) delete r;
  99. 	}
  100. };
  101.  
  102. int Tc,n,k[N],j,q,l[N],r[N],ans[N];
  103. vector<int> v;
  104. map<int,int> mep;
  105.  
  106. int main()
  107. {
  108. 	scanf("%d",&Tc);
  109. 	for(int tc=1;tc<=Tc;tc++){
  110. 		printf("Case #%d:\n", tc);
  111. 		int idx = 1;
  112. 		v.clear();
  113. 		mep.clear();
  114. 		scanf("%d %d",&n,&q);
  115. 		for(int i=0;i<n;i++){
  116. 			scanf("%d",&a[i+1]);
  117. 			v.push_back(a[i+1]);
  118. 		}
  119. 		for(int i=0;i<q;i++){
  120. 			scanf("%d %d %d",&l[i],&r[i],&k[i]);
  121. 		}
  122. 		sort(v.begin(), v.end());
  123. 		for(int i=0;i<v.size();i++){
  124. 			if(mep.find(v[i])==mep.end()) mep[v[i]] = idx, ans[idx++] = v[i];
  125. 		}
  126. 		for(int i=0;i<n;i++){
  127. 			a[i+1] = mep[a[i+1]];
  128. 		}
  129. 		wavelet_tree T(a+1, a+n+1, 1, MAX);
  130. 		for(int i=0;i<q;i++){
  131. 			// cout<<l[i]<<" "<<r[i]<<" "<<k[i]<<endl;
  132. 			printf("%d\n", ans[T.kth(l[i], r[i], k[i])]);
  133. 		}
  134. 		// delete T.l;
  135. 		// delete T.r;
  136. 	}
  137. 	return 0;
  138. } 
  139.  
  140.  
Success #stdin #stdout 0s 19560KB
comments (?)
stdin 
4
10 3
5 7 10 2 1 1 4 6 13 3
1 10 3
2 6 4
7 10 1
10 3
5 7 10 2 1 1 4 6 13 3
1 10 3
2 6 4
7 10 1
5 1
1002 49301 2339 1004 17
2 4 1
6 2
18 3 74 11 15 11
2 6 3
1 4 3
stdout 
Case #1:
2
7
3
Case #2:
2
7
3
Case #3:
1004
Case #4:
11
18
https://ideone.com/U2977W
Wavelet Tree https://p...content-available-to-author-only...j.com/problem/INC2015H
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!