fork(1) download
copy 
  1. /// Add / remove elements
  2. /// No of elements < X
  3. /// k-th smallest element
  4. /// min / max
  5. /// Time complexity = log(n)
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11. typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  12. int main()
  13. {
  14.     /// Add elements in any random order
  15.     pbds A;
  16.     A.insert(11);
  17.     A.insert(1);
  18.     A.insert(5);
  19. 	A.insert(3);
  20. 	A.insert(7);
  21. 	A.insert(9);
  22. 	A.insert(3);
  23.  
  24. 	//Total contents
  25. 	cout << "1, 3, 3 ,5, 7, 9, 11" << endl;
  26.  
  27. 	//K-th smallest
  28. 	int k = 3;
  29. 	cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;
  30.  
  31. 	//NO OF ELEMENTS < X
  32. 	int X = 9;
  33.  
  34. 	cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
  35.  
  36. 	//DELETE Elements
  37.     cout << "Deleted 3" << endl;
  38.     A.erase(A.find(3));
  39.  
  40.     //Total contents
  41. 	cout << "1, 3 ,5 ,7, 9, 11" << endl;
  42.  
  43. 	//NO OF ELEMENTS < X
  44. 	X = 9;
  45.  
  46. 	cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
  47.  
  48.  
  49. 	k = 3;
  50. 	cout << k << "rd smallest: " << *A.find_by_order(k-1) << endl;
  51.  
  52.  
  53.  
  54. 	return 0;
  55. }
  56.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1, 3, 3 ,5, 7, 9, 11
3rd smallest: 3
No of elements less than 9 are 5
Deleted 3
1, 3 ,5 ,7, 9, 11
No of elements less than 9 are 5
3rd smallest: 3
https://ideone.com/Oessur
language:
C++ (gcc 8.3)
created:
4 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!