Advertisement
Guest User

Untitled

a guest
Apr 26th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.60 KB | None | 0 0
  1. /*
  2. Solves CF 863D
  3. Given an array
  4. 2 types of updates
  5. 1. Reverse a segment
  6. 2. Cyclically shift a segment to the right
  7. */
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10.  
  11. typedef struct item * pitem;
  12. struct item {
  13. int prior, value, cnt;
  14. bool rev;
  15. item(int value):prior(rand()), value(value) {
  16. cnt = 0;
  17. rev = 0;
  18. l = r = nullptr;
  19. }
  20. pitem l, r;
  21. };
  22.  
  23. namespace Treap {
  24.  
  25. int cnt (pitem it) {
  26. return it != nullptr? it->cnt : 0;
  27. }
  28. void upd_cnt (pitem it) {
  29. if (it!=nullptr)
  30. it->cnt = cnt(it->l) + cnt(it->r) + 1;
  31. }
  32. void push (pitem it) {
  33. if (it != nullptr && it->rev == true) {
  34. it->rev = false;
  35. swap (it->l, it->r);
  36. if (it->l) it->l->rev ^= true;
  37. if (it->r) it->r->rev ^= true;
  38. }
  39. }
  40. void merge (pitem & t, pitem l, pitem r) {
  41. push (l);
  42. push (r);
  43. if (l==nullptr || r==nullptr)
  44. t = (l!=nullptr) ? l : r;
  45. else if (l->prior > r->prior)
  46. merge (l->r, l->r, r), t = l;
  47. else
  48. merge (r->l, l, r->l), t = r;
  49. upd_cnt (t);
  50. }
  51.  
  52. void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
  53. if (t==nullptr) {
  54. l = r = nullptr;
  55. return;
  56. }
  57. push (t);
  58. int cur_key = add + cnt(t->l);
  59. if (key <= cur_key)
  60. split (t->l, l, t->l, key, add), r = t;
  61. else
  62. split (t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t;
  63. upd_cnt (t);
  64. }
  65.  
  66. void reverse (pitem &t, int l, int r) {
  67. pitem t1, t2, t3;
  68. split (t, t1, t2, l);
  69. split (t2, t2, t3, r-l+1);
  70. t2->rev ^= true;
  71. merge (t, t1, t2);
  72. merge (t, t, t3);
  73. }
  74.  
  75. void insert (pitem & t, int key, int value) {
  76. pitem x = new item(value);
  77. pitem L, R;
  78. split(t, L, R, key);
  79. merge(L, L, x);
  80. merge(t, L, R);
  81. upd_cnt(t);
  82. }
  83.  
  84. void erase (pitem & t, int key) {
  85. assert(cnt(t) > key);
  86. pitem L, MID, R;
  87. split(t, L, MID, key);
  88. split(MID, MID, R, 1);
  89. merge(t, L, R);
  90. delete MID;
  91. upd_cnt(t);
  92. }
  93.  
  94. void cyclicShift(pitem &t, int l, int r)
  95. {
  96. assert(0 <= l && r < cnt(t));
  97. pitem L, MID, R;
  98. split(t, L, MID, r);
  99. split(MID, MID, R, 1);
  100. merge(t, L, R);
  101. assert(MID!=nullptr);
  102. insert(t, l, MID->value);
  103. delete MID;
  104. upd_cnt(t);
  105. }
  106.  
  107. void output (pitem t, vector< int >&v) {
  108. if (t==nullptr) return;
  109. push (t);
  110. output (t->l, v);
  111. v.push_back(t->value);
  112. output (t->r, v);
  113. }
  114.  
  115. void output2 (pitem t) {
  116. if (t==nullptr) return;
  117. push (t);
  118. cout << "(";
  119. output2 (t->l);
  120. cout << (t->value);
  121. output2 (t->r);
  122. cout << ")";
  123. }
  124. }
  125.  
  126. int main()
  127. {
  128. std::ios_base::sync_with_stdio(false);
  129.  
  130. srand(time(0));
  131. pitem tr = nullptr;
  132.  
  133. int n, q, m;
  134. cin >> n >> q >> m;
  135.  
  136. for (int i = 0; i < n; i++) {
  137. int x;
  138. cin >> x;
  139. Treap::insert(tr, i, x);
  140. }
  141. while (q--) {
  142. int t, l, r;
  143. cin >> t >> l >> r;
  144. l--; r--;
  145. if (l==r) continue;
  146. if (t==1) Treap::cyclicShift(tr, l, r);
  147. else Treap::reverse(tr, l, r);
  148. }
  149.  
  150. vector< int >b;
  151. Treap::output(tr, b);
  152. while (m--) {
  153. int x;
  154. cin >> x; x--;
  155. cout << b[x] << " ";
  156. }
  157. return 0;
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement