View difference between Paste ID: dr9rhYZ1 and 7K5Eb0th

 #include<bits/stdc++.h>
 
 #define endl "\n"
 using namespace std;
 using ll = long long;
 using ld = long double;
 using pii = pair<int, int>;
 
 constexpr int N = 1e6 + 5;
 
 constexpr ll mod = 1e9 + 9;
 
 int n, l, r, type, v;
 string init;
 
 ll deg[N];
 
 ll mul(ll l, ll r){
   return (l * r) % mod;
 }
 
 ll sum(ll l, ll r){
   return (l + r) % mod;
 }
 
 struct Treap{
   struct Node{
     bool isrev;
     char val;
     int sz;
     int pri;
     Node *l, *r;
     ll hash;
     ll revhash;
     Node(char a = '0', Node *le = nullptr, Node *ri = nullptr) :
       val(a), pri((rand() << 16) + rand()), sz(1),
       hash(a - 'a' + 1), revhash(a - 'a' + 1),
       l(le), r(ri) {};
   };
 
   using pN = Node*;
   using pNN =  pair<pN, pN>;
 
   Node buff[N];
   pN root = nullptr;
   int st = 0;
 
   pN newN(char val){
     buff[st] = Node(val);
     return &buff[st++];
   }
 
   int getsz(pN v){
     return v == nullptr ? 0 : v -> sz;
   }
 
   ll gethash(pN v){
     return v == nullptr ? 0 : v -> hash;
   }
 
   ll getrevhash(pN v){
     return v == nullptr ? 0 : v -> hash;
   }
 
   void recalc(pN v){
     v -> sz = getsz(v -> l) + getsz(v -> r) + 1;
     v -> hash = sum(sum(gethash(v -> l), mul(gethash(v -> r),
     deg[getsz(v -> l) + 1])), mul((v -> val - 'a' + 1ll), deg[getsz(v -> l)]));
     v -> revhash = sum(sum(getrevhash(v -> r), mul(getrevhash(v -> l),
     deg[getsz(v -> r) + 1])), mul((v -> val - 'a' + 1ll), deg[getsz(v -> r)]));
     return;
   }
 
   pNN split(pN v, int k){
     if (k == 0)
       return {nullptr, v};
     push(v);
     if (getsz(v -> l) >= k){
       auto p = split(v -> l, k);
       v -> l = p.second;
       recalc(v);
       return {p.first, v};
     }
     else {
       auto p = split(v -> r, k - getsz(v -> l) - 1);
       v -> r = p.first;
       recalc(v);
       return {v, p.second};
     }
   }
 
   pN merge(pN l, pN r){
     if (l == nullptr)
       return r;
     if (r == nullptr)
       return l;
     if (l -> pri < r -> pri){
       push(l);
       l -> r = merge(l -> r, r);
       recalc(l);
       return l;
     }
     else {
       push(r);
       r -> l = merge(l, r -> l);
       recalc(r);
       return r;
     }
   }
 
   void insert(int k, char val){
     auto p1 = split(root, k);
     auto v = newN(val);
     root = merge(merge(p1.first, v), p1.second);
     return;
   }
 
   void reverse(pN v){
     if (v == nullptr)
       return;
     v -> isrev ^= 1;
     swap(v -> hash, v -> revhash);
     swap(v -> l, v -> r);
   }
 
   void push(pN v){
     if (v == nullptr)
       return;
     if (v -> isrev){
       reverse(v -> l);
       reverse(v -> r);
       v -> isrev = 0;
       swap(v -> hash, v -> revhash);
     }
     return;
   }
 
   void rev(int l, int r){
     auto p1 = split(root, r);
     auto p2 = split(p1.first, l - 1);
     reverse(p2.second);
     root = merge(merge(p2.first, p2.second), p1.second);
     return;
   }
 
   void clear(){
     st = 0;
     root = nullptr;
   }
 
 } tr1, tr2; // tr2 is copy of tr1 (only difference is priority)
 
 bool check(int len, int l, int r){
   auto p1 = tr1.split(tr1.root, l - 1);
   auto p2 = tr2.split(tr2.root, r - 1);
   auto p3 = tr1.split(p1.second, len);
   auto p4 = tr2.split(p2.second, len);
   bool ans = (tr1.gethash(p3.first) == tr2.gethash(p4.first));
   tr1.root = tr1.merge(p1.first, tr1.merge(p3.first, p3.second));
   tr2.root = tr2.merge(p2.first, tr2.merge(p4.first, p4.second));
   return ans;
 }
 
 int findk(int ql, int qr){
   int l = 0, r = tr1.getsz(tr1.root) - qr + 1, mid, ans = 0;
   while (l <= r){
     mid = (l + r) >> 1;
     if (check(mid, ql, qr))
       ans = mid, l = mid + 1;
     else r = mid - 1;
   }
   return ans;
 }
 
 
 void Solve(){
   deg[0] = 1ll;
   for (int i = 1; i < N; i++)
     deg[i] = mul(deg[i - 1], 31ll);
   cin >> init;
   for (int i = 0; i < init.size(); i++){
     tr1.insert(i, init[i]);
     tr2.insert(i, init[i]);
   }
   cin >> n;
   while (n--){
     cin >> type >> l >> r;
     if (type == 1){
       tr1.rev(l, r);
       tr2.rev(l, r);
     }
     else
       cout << findk(l, r) << endl;
   }
 }
 
 int main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   Solve();
   return 0;
 }