fork(8) download
copy 
  1. #include <bits/stdc++.h>
  2. //Complete code at ideone.com/Tkters
  3. //This code has comments and is for understanding the blog 
  4. using namespace std;
  5. #define gc getchar_unlocked
  6. #define fo(i,n) for(i=0;i<n;i++)
  7. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  8. #define ll long long
  9. #define si(x)	scanf("%d",&x)
  10. #define sl(x)	scanf("%lld",&x)
  11. #define ss(s)	scanf("%s",s)
  12. #define pi(x)	printf("%d\n",x)
  13. #define pl(x)	printf("%lld\n",x)
  14. #define ps(s)	printf("%s\n",s)
  15. #define deb(x) cout << #x << "=" << x << endl
  16. #define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
  17. #define pb push_back
  18. #define mp make_pair
  19. #define F first
  20. #define S second
  21. #define all(x) x.begin(), x.end()
  22. #define clr(x) memset(x, 0, sizeof(x))
  23. #define sortall(x) sort(all(x))
  24. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  25. #define PI 3.1415926535897932384626
  26. typedef pair<int, int>	pii;
  27. typedef pair<ll, ll>	pl;
  28. typedef vector<int>		vi;
  29. typedef vector<ll>		vl;
  30. typedef vector<pii>		vpii;
  31. typedef vector<pl>		vpl;
  32. typedef vector<vi>		vvi;
  33. typedef vector<vl>		vvl;
  34. int mpow(int base, int exp); 
  35. void ipgraph(int m);
  36. void dfs(int u, int par);
  37. const int mod = 1000000007;
  38. const int N = 3e5, M = N;
  39. //=======================
  40.  
  41. vi g[N];
  42. int a[N];
  43. const int MAX = 1e6;
  44. struct wavelet_tree{
  45. 	#define vi vector<int>
  46. 	#define pb push_back
  47. 	int lo, hi;
  48. 	wavelet_tree *l, *r;
  49. 	vi b;
  50.  
  51. 	//nos are in range [x,y]
  52. 	//array indices are [from, to)
  53. 	wavelet_tree(int *from, int *to, int x, int y){
  54. 		lo = x, hi = y;
  55. 		if(lo == hi or from >= to) return;
  56.  
  57. 		int mid = (lo+hi)/2;
  58. 		auto f = [mid](int x){
  59. 			return x <= mid;
  60. 		};
  61. 		b.reserve(to-from+1);
  62. 		b.pb(0);
  63. 		//b[i] = no of elements from first "i" elements that go to left node
  64. 		for(auto it = from; it != to; it++)
  65. 			b.pb(b.back() + f(*it));
  66.  
  67. 		//see how lambda function is used here	
  68. 		auto pivot = stable_partition(from, to, f);
  69. 		l = new wavelet_tree(from, pivot, lo, mid);
  70. 		r = new wavelet_tree(pivot, to, mid+1, hi);
  71. 	}
  72.  
  73. 	//kth smallest element in [l, r]
  74. 	int kth(int l, int r, int k){
  75. 		if(l > r) return 0;
  76. 		if(lo == hi) return lo;
  77. 		//how many nos are there in left node from [l, r]
  78. 		int inleft = b[r] - b[l-1];
  79. 		int lb = b[l-1]; //amt of nos from first (l-1) nos that go in left 
  80. 		int rb = b[r]; //amt of nos from first (r) nos that go in left
  81. 		//so [lb+1, rb] represents nos from [l, r] that go to left
  82. 		if(k <= inleft) return this->l->kth(lb+1, rb , k);
  83.  
  84. 		//(l-1-lb) is amt of nos from first (l-1) nos that go to right
  85. 		//(r-rb) is amt of nos from first (r) nos that go to right
  86. 		//so [l-lb, r-rb] represents nos from [l, r] that go to right
  87. 		return this->r->kth(l-lb, r-rb, k-inleft);
  88. 	}
  89. 	~wavelet_tree(){
  90. 		delete l;
  91. 		delete r;
  92. 	}
  93.  
  94. };
  95. int main()
  96. {
  97. 	ios_base::sync_with_stdio(false);
  98. 	cin.tie(NULL);
  99. 	srand(time(NULL));
  100. 	int i,n,k,j,q,l,r;
  101. 	cin >> n;
  102. 	fo(i, n) cin >> a[i+1];
  103. 	wavelet_tree T(a+1, a+n+1, 1, MAX);
  104. 	cin >> q;
  105. 	while(q--){
  106. 		cin >> l >> r >> k;
  107. 		cout << T.kth(l, r, k) << endl;
  108. 	}
  109. 	return 0;
  110. } 
  111.  
  112.  
Success #stdin #stdout 0s 24256KB
comments (?)
stdin
copy 
7
1 2 3 3 5 4 2
2
5 7 1
5 7 2
stdout
copy 
2
4
https://ideone.com/joqdYj
wavelet tree, tutorial
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!