Advertisement
limimage

TASKE9(((

Oct 5th, 2019
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.15 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define endl "\n"
  4. using namespace std;
  5. using ll = long long;
  6. using ld = long double;
  7. using pii = pair<int, int>;
  8.  
  9. constexpr int N = 1e6 + 5;
  10.  
  11. constexpr ll mod = 1e9 + 9;
  12.  
  13. int n, l, r, type, v;
  14. string init;
  15.  
  16. ll deg[N];
  17.  
  18. ll mul(ll l, ll r){
  19. return (l * r) % mod;
  20. }
  21.  
  22. ll sum(ll l, ll r){
  23. return (l + r) % mod;
  24. }
  25.  
  26. struct Treap{
  27. struct Node{
  28. bool isrev;
  29. char val;
  30. int sz;
  31. int pri;
  32. Node *l, *r;
  33. ll hash;
  34. ll revhash;
  35. Node(char a = '0', Node *le = nullptr, Node *ri = nullptr) :
  36. val(a), pri((rand() << 16) + rand()), sz(1),
  37. hash(a - 'a' + 1), revhash(a - 'a' + 1),
  38. l(le), r(ri) {};
  39. };
  40.  
  41. using pN = Node*;
  42. using pNN = pair<pN, pN>;
  43.  
  44. Node buff[N];
  45. pN root = nullptr;
  46. int st = 0;
  47.  
  48. pN newN(char val){
  49. buff[st] = Node(val);
  50. return &buff[st++];
  51. }
  52.  
  53. int getsz(pN v){
  54. return v == nullptr ? 0 : v -> sz;
  55. }
  56.  
  57. ll gethash(pN v){
  58. return v == nullptr ? 0 : v -> hash;
  59. }
  60.  
  61. ll getrevhash(pN v){
  62. return v == nullptr ? 0 : v -> hash;
  63. }
  64.  
  65. void recalc(pN v){
  66. v -> sz = getsz(v -> l) + getsz(v -> r) + 1;
  67. v -> hash = sum(sum(gethash(v -> l), mul(gethash(v -> r),
  68. deg[getsz(v -> l) + 1])), mul((v -> val - 'a' + 1ll), deg[getsz(v -> l)]));
  69. v -> revhash = sum(sum(getrevhash(v -> r), mul(getrevhash(v -> l),
  70. deg[getsz(v -> r) + 1])), mul((v -> val - 'a' + 1ll), deg[getsz(v -> r)]));
  71. return;
  72. }
  73.  
  74. pNN split(pN v, int k){
  75. if (k == 0)
  76. return {nullptr, v};
  77. push(v);
  78. if (getsz(v -> l) >= k){
  79. auto p = split(v -> l, k);
  80. v -> l = p.second;
  81. recalc(v);
  82. return {p.first, v};
  83. }
  84. else {
  85. auto p = split(v -> r, k - getsz(v -> l) - 1);
  86. v -> r = p.first;
  87. recalc(v);
  88. return {v, p.second};
  89. }
  90. }
  91.  
  92. pN merge(pN l, pN r){
  93. if (l == nullptr)
  94. return r;
  95. if (r == nullptr)
  96. return l;
  97. if (l -> pri < r -> pri){
  98. push(l);
  99. l -> r = merge(l -> r, r);
  100. recalc(l);
  101. return l;
  102. }
  103. else {
  104. push(r);
  105. r -> l = merge(l, r -> l);
  106. recalc(r);
  107. return r;
  108. }
  109. }
  110.  
  111. void insert(int k, char val){
  112. auto p1 = split(root, k);
  113. auto v = newN(val);
  114. root = merge(merge(p1.first, v), p1.second);
  115. return;
  116. }
  117.  
  118. void reverse(pN v){
  119. if (v == nullptr)
  120. return;
  121. v -> isrev ^= 1;
  122. swap(v -> hash, v -> revhash);
  123. swap(v -> l, v -> r);
  124. }
  125.  
  126. void push(pN v){
  127. if (v == nullptr)
  128. return;
  129. if (v -> isrev){
  130. reverse(v -> l);
  131. reverse(v -> r);
  132. v -> isrev = 0;
  133. swap(v -> hash, v -> revhash);
  134. }
  135. return;
  136. }
  137.  
  138. void rev(int l, int r){
  139. auto p1 = split(root, r);
  140. auto p2 = split(p1.first, l - 1);
  141. reverse(p2.second);
  142. root = merge(merge(p2.first, p2.second), p1.second);
  143. return;
  144. }
  145.  
  146. void clear(){
  147. st = 0;
  148. root = nullptr;
  149. }
  150.  
  151. } tr1, tr2; // tr2 is copy of tr1 (only difference is priority)
  152.  
  153. bool check(int len, int l, int r){
  154. auto p1 = tr1.split(tr1.root, l - 1);
  155. auto p2 = tr2.split(tr2.root, r - 1);
  156. auto p3 = tr1.split(p1.second, len);
  157. auto p4 = tr2.split(p2.second, len);
  158. bool ans = (tr1.gethash(p3.first) == tr2.gethash(p4.first));
  159. tr1.root = tr1.merge(p1.first, tr1.merge(p3.first, p3.second));
  160. tr2.root = tr2.merge(p2.first, tr2.merge(p4.first, p4.second));
  161. return ans;
  162. }
  163.  
  164. int findk(int ql, int qr){
  165. int l = 0, r = tr1.getsz(tr1.root) - qr + 1, mid, ans = 0;
  166. while (l <= r){
  167. mid = (l + r) >> 1;
  168. if (check(mid, ql, qr))
  169. ans = mid, l = mid + 1;
  170. else r = mid - 1;
  171. }
  172. return ans;
  173. }
  174.  
  175.  
  176. void Solve(){
  177. deg[0] = 1ll;
  178. for (int i = 1; i < N; i++)
  179. deg[i] = mul(deg[i - 1], 31ll);
  180. cin >> init;
  181. for (int i = 0; i < init.size(); i++){
  182. tr1.insert(i, init[i]);
  183. tr2.insert(i, init[i]);
  184. }
  185. cin >> n;
  186. while (n--){
  187. cin >> type >> l >> r;
  188. if (type == 1){
  189. tr1.rev(l, r);
  190. tr2.rev(l, r);
  191. }
  192. else
  193. cout << findk(l, r) << endl;
  194. }
  195. }
  196.  
  197. int main(){
  198. ios::sync_with_stdio(false);
  199. cin.tie(nullptr);
  200. cout.tie(nullptr);
  201. Solve();
  202. return 0;
  203. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement