fork(2) download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. using namespace std;
  4.  
  5. const int INF = 1e9 + 7;
  6. const int MAX_N = 1e5 + 5;
  7.  
  8. //-------------------------------------------------
  9.  
  10. struct WaveletTree {
  11. 	private:
  12. 		struct Node;
  13. 		void BuildTree(Node *node, int low, int high);
  14. 		int FindKth(Node *node, int le, int ri, int k);
  15.  
  16. 		Node *root;
  17.  
  18. 	public:
  19. 		WaveletTree(const vector< int > &numbers);
  20. 		int FindKth(int le, int ri, int k);
  21. 		void Build(const vector< int > &v);
  22. };
  23.  
  24. struct WaveletTree::Node {
  25. 	vector< int > a, b;
  26. 	Node *left, *right;	
  27.  
  28. 	Node();
  29. };
  30.  
  31. WaveletTree::Node::Node() : left(nullptr), right(nullptr) {
  32. 	a.clear();
  33. 	b.clear();
  34. }
  35.  
  36. WaveletTree::WaveletTree(const vector< int > &numbers) {
  37. 	Build(numbers);
  38. }
  39.  
  40. void WaveletTree::BuildTree(Node *node, int low, int high) {
  41. 	node -> b.push_back(0);
  42.  
  43. 	if(node -> a.size() == 1 || low == high) {
  44. 		return;
  45. 	}
  46.  
  47. 	int mid = (low + high) / 2, cntSmallerOrEqual = 0;
  48.  
  49. 	node -> left = new Node();
  50. 	node -> right = new Node();
  51.  
  52. 	node -> left -> a.push_back(INF);
  53. 	node -> right -> a.push_back(INF);
  54.  
  55. 	for(int num : node -> a) {
  56. 		if(num == INF) {
  57. 			continue;
  58. 		}
  59.  
  60. 		if(num <= mid) {
  61. 			node -> left -> a.push_back(num);
  62. 			cntSmallerOrEqual++;
  63. 		}
  64. 		else {
  65. 			node -> right -> a.push_back(num);
  66. 		}
  67.  
  68. 		node -> b.push_back(cntSmallerOrEqual);
  69. 	}
  70.  
  71. 	BuildTree(node -> left, low, mid);
  72. 	BuildTree(node -> right, mid + 1, high);
  73. }
  74.  
  75. void WaveletTree::Build(const vector< int > &v) {
  76. 	int maxNum = -INF, minNum = INF;
  77.  
  78. 	root = new Node();
  79. 	root -> a.push_back(INF);
  80.  
  81. 	for(int num : v) {
  82. 		root -> a.push_back(num);
  83.  
  84. 		minNum = min(minNum, num);
  85. 		maxNum = max(maxNum, num);
  86. 	}
  87.  
  88. 	BuildTree(root, minNum, maxNum);
  89. }
  90.  
  91. int WaveletTree::FindKth(Node *node, int le, int ri, int k) {
  92. 	if(le == ri) {
  93. 		return node -> a[le];
  94. 	}
  95.  
  96. 	int goingLeft = node -> b[ri] - node -> b[le - 1];
  97.  
  98. 	if(goingLeft >= k) {
  99. 		return FindKth(node -> left, node -> b[le - 1] + 1, node -> b[ri], k);
  100. 	}
  101. 	else {
  102. 		int newLe = le - node -> b[le - 1];
  103. 		int newRi = ri - node -> b[ri];
  104. 		int newK = k - goingLeft;
  105.  
  106. 		return FindKth(node -> right, newLe, newRi, newK);
  107. 	}
  108. }
  109.  
  110. int WaveletTree::FindKth(int le, int ri, int k) {
  111. 	return FindKth(root, le, ri, k);
  112. }
  113.  
  114. //-------------------------------------------------
  115.  
  116. int fromNewToOld[MAX_N];
  117.  
  118. void Compress(vector< int > &v) {
  119. 	vector< int > numbers = v;
  120. 	sort(numbers.begin(), numbers.end());
  121.  
  122. 	for(int i = 0; i < v.size(); i++) {
  123. 		int oldValue = v[i];
  124. 		v[i] = lower_bound(numbers.begin(), numbers.end(), oldValue) - numbers.begin() + 1;
  125.  
  126. 		fromNewToOld[v[i]] = oldValue;
  127. 	}
  128. }
  129.  
  130. int main() {
  131. 	ios_base::sync_with_stdio(false);
  132. 	cin.tie(NULL);
  133. 	cout.tie(NULL);
  134.  
  135. 	int n, m;
  136. 	cin >> n >> m;
  137.  
  138. 	vector< int > v(n);
  139. 	for(int i = 0; i < n; i++) {
  140. 		cin >> v[i];
  141. 	}
  142.  
  143. 	Compress(v);
  144.  
  145. 	WaveletTree waveletTree = WaveletTree(v);
  146.  
  147. 	for(int i = 0; i < m; i++) {
  148. 		int le, ri, k;
  149. 		cin >> le >> ri >> k;
  150.  
  151. 		cout << fromNewToOld[waveletTree.FindKth(le, ri, k)] << endl;
  152. 	}
  153.  
  154. 	return 0;
  155. }
Runtime error #stdin #stdout 0s 4516KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/xzqIGH
language:
C++14 (gcc 8.3)
created:
8 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!