Advertisement
Guest User

Untitled

a guest
Oct 20th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <random>
  3.  
  4. using namespace std;
  5.  
  6. struct vertice{
  7. int x;
  8. int y;
  9. int c;
  10. vertice* l;
  11. vertice* r;
  12. vertice (){
  13. x = -1;
  14. y = rand();
  15. c = 0;
  16. l = NULL;
  17. r = NULL;
  18. }
  19. vertice (int a){
  20. x = -1;
  21. y = rand();
  22. c = a;
  23. l = NULL;
  24. r = NULL;
  25. }
  26. };
  27.  
  28. vertice* root = NULL;
  29.  
  30. int c(vertice* v){
  31. if (v == NULL){
  32. return 0;
  33. }
  34. return v -> c;
  35. }
  36.  
  37. void change(vertice* v){
  38. if (v == NULL){
  39. return;
  40. }
  41. v -> c = c(v -> l) + c(v -> r);
  42. }
  43.  
  44. pair < vertice*, vertice* > split (vertice* now, int a){
  45. if (now == NULL){
  46. return {NULL, NULL};
  47. }
  48. if (c(now -> l) < a){
  49. auto tmp = split(now -> r, a);
  50. change(tmp.first);
  51. change(tmp.second);
  52. now -> r = tmp.first;
  53. change(now);
  54. return {now, tmp.second};
  55. }
  56. auto tmp = split(now -> l, a);
  57. change(tmp.first);
  58. change(tmp.second);
  59. now -> l = tmp.second;
  60. change(now);
  61. return {tmp.first, now};
  62. }
  63.  
  64. vertice* merge(vertice* t1, vertice* t2){
  65. if (t1 == NULL){
  66. return t2;
  67. }
  68. if (t2 == NULL){
  69. return t1;
  70. }
  71. if (t1 -> y > t2 -> y){
  72. t2 -> l = merge(t1, t2 -> l);
  73. change(t2);
  74. return t2;
  75. }
  76. t1 -> r = merge(t1 -> r, t2);
  77. change(t1);
  78. return t1;
  79. }
  80.  
  81. vertice* add(int a, vertice* now){
  82. auto tmp = split(root, a);
  83. vertice* tmp2 = new vertice(a);
  84. return merge(merge(tmp.first, tmp2), tmp.second);
  85. }
  86.  
  87. vertice* erase(int a){
  88. auto tl = split(root, a);
  89. auto tr = split(tl.second, a + 1);
  90. return merge(tl.first, tr.second);
  91. }
  92.  
  93. void print(vertice* now, int sum){
  94. if (now == NULL){
  95. return;
  96. }
  97. print(now -> l, sum);
  98. cout << sum + c(now -> l) + 1 << " ";
  99. print(now -> r, sum + 1 + c(now -> l));
  100. }
  101.  
  102. int main(){
  103. int n;
  104. cin >> n;
  105. int a;
  106. for (int i = 0; i < n; i++){
  107. cin >> a;
  108. root = add(a, root);
  109. }
  110. print(root, 0);
  111. return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement