Advertisement
Guest User

Untitled

a guest
Oct 19th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. struct node{
  7. int y, size, val, min_v;
  8. bool reversed;
  9. node * left, * right;
  10. };
  11.  
  12.  
  13. void push(node * &v){
  14. if(v -> left)
  15. v -> left -> reversed ^= true;
  16. if(v -> right)
  17. v -> right -> reversed ^= true;
  18. }
  19.  
  20. inline void rev(node * &v){
  21. if(v -> reversed){
  22. v -> reversed = false;
  23. if(v -> right != nullptr && v -> left != nullptr){
  24. swap(v -> right, v -> left);
  25. }
  26. push(v);
  27. }
  28. }
  29.  
  30.  
  31.  
  32. void update(node * &v) {
  33. if (!v) return;
  34. rev(v);
  35. v->size = (v->left ? v->left->size : 0) + (v->right ? v->right->size : 0) + 1;
  36. v -> min_v = min(min((v -> left ? v -> left -> min_v : 1000 * 1000 * 1000 + 10), (v -> right ? v -> right -> min_v : 1000 * 1000 * 1000 + 10)), v -> val);
  37. // v->sum = (v->left ? v->left->sum : 0) + v->val + (v->right ? v->right->sum : 0);
  38. }
  39.  
  40.  
  41. int my_rand() {
  42. return (rand() << 16) | rand();
  43. }
  44.  
  45. node * merge(node * left, node * right) {
  46. if (!left) return right;
  47. if (!right) return left;
  48. if (left->y > right->y) {
  49. left->right = merge(left->right, right);
  50. update(left);
  51. return left;
  52. } else {
  53. right->left = merge(left, right->left);
  54. update(right);
  55. return right;
  56. }
  57. }
  58.  
  59. pair<node *, node *> split(node * tree, int x) {
  60. if (!tree) return {tree, tree};
  61. int ind = tree->left ? tree->left->size : 0;
  62. if (ind > x) {
  63. auto res = split(tree->left, x);
  64. tree->left = res.second;
  65. update(tree);
  66. return {res.first, tree};
  67. } else {
  68. auto res = split(tree->right, x - ind - 1);
  69. tree->right = res.first;
  70. update(tree);
  71. return {tree, res.second};
  72. }
  73. }
  74.  
  75. node * add(node * tree, node * x, int pos) {
  76. if (!tree)
  77. return x;
  78. if (tree->y > x->y) {
  79. int ind = tree->left ? tree->left->size : 0;
  80. if (ind >= pos) {
  81. tree->left = add(tree->left, x, pos);
  82. update(tree);
  83. return tree;
  84. } else {
  85. tree->right = add(tree->right, x, pos - ind - 1);
  86. update(tree);
  87. return tree;
  88. }
  89. } else {
  90. auto res = split(tree, pos - 1);
  91. tree = x;
  92. tree->left = res.first;
  93. tree->right = res.second;
  94. update(tree);
  95. return tree;
  96. }
  97. }
  98.  
  99.  
  100.  
  101. int main(void){
  102. int n, m;
  103. cin >> n >> m;
  104. node * root = nullptr;
  105. int * a = new int[n];
  106. for(int i = 0; i < n; ++i){
  107. cin >> a[i];
  108. }
  109. for(int i = 0; i < n; ++i){
  110. node * v = new node({my_rand(), 1, a[i], a[i], false, nullptr, nullptr});
  111. root = add(root, v, i);
  112. }
  113. char c;
  114. int x, y;
  115. for(int i = 0; i < m; ++i){
  116. cin >> c >> x >> y;
  117. x--;
  118. y--;
  119. if(x > y){
  120. swap(x, y);
  121. }
  122. if(c == '1'){
  123. auto tree1 = split(root, y);
  124. pair<node *, node *> tree2;
  125. tree2 = split(tree1.first, x - 1);
  126. tree2.second -> reversed = true;
  127. rev(tree2.second);
  128. root = merge(merge(tree2.first, tree2.second), tree1.second);
  129. }
  130. if(c == '2'){
  131. auto tree1 = split(root, y);
  132. pair<node *, node *> tree2;
  133. tree2 = split(tree1.first, x - 1);
  134. cout << tree2.second -> min_v << endl;
  135. root = merge(merge(tree2.first, tree2.second), tree1.second);
  136. }
  137. }
  138.  
  139.  
  140. return 0;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement