AhmedAshraff

Untitled

Sep 18th, 2024
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.48 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6.  
  7. #define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
  8. #define ll long long
  9. #define ld long double
  10. #define sz(s) (int)(s).size()
  11. #define all(s) (s).begin(),(s).end()
  12. #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
  13. using namespace __gnu_pbds;
  14. using namespace std;
  15.  
  16. void File();
  17. void sol();
  18. struct Node {
  19.     int val = 0, lazy = 0;
  20. } neutral;
  21.  
  22. const int N = 2e5 + 5, MOD = 1e9 + 7;
  23. int pw[N], inv[N], BASE;
  24. int fix(ll x, int mod) {
  25.     x %= mod;
  26.     if (x < 0) x += mod;
  27.     return x;
  28. }
  29. struct segtree {
  30.     segtree *left = nullptr, *right = nullptr;
  31.     Node node = {};
  32.     int start, end;
  33.  
  34.     segtree(int l = 0, int r = 0) : start(l), end(r) {}
  35.  
  36.     void extend() {
  37.         if (left == nullptr) {
  38.             int mid = (start + end) >> 1;
  39.             left = new segtree(start, mid);
  40.             right = new segtree(mid + 1, end);
  41.         }
  42.     }
  43.  
  44.     Node pushup(Node a, Node b) {
  45.         Node ret;
  46.         ret.val = fix(0ll+a.val + b.val,MOD);
  47.         return ret;
  48.     }
  49.  
  50.     void pushdown() {
  51.         node.val =fix(0ll+node.val+node.lazy,MOD);
  52.         if (start != end) {
  53.             extend();
  54.             left->node.lazy =fix(left->node.lazy+node.lazy,MOD);
  55.             right->node.lazy =fix(right->node.lazy+node.lazy,MOD);
  56.         }
  57.         node.lazy = 0;
  58.     }
  59.  
  60.     void update(int l, int r, int val) {
  61.         pushdown();
  62.         if (start > r || end < l) return;
  63.         if (start >= l && end <= r) {
  64.             node.lazy = val;
  65.             pushdown();
  66.             return;
  67.         }
  68.         extend();
  69.         left->update(l, r, val);
  70.         right->update(l, r, val);
  71.         node = pushup(left->node, right->node);
  72.     }
  73.  
  74.     Node query(int l, int r) {
  75.         pushdown();
  76.         if (r < start || end < l) return neutral;
  77.         if (l <= start && end <= r) return node;
  78.         extend();
  79.         Node ret = pushup(left->query(l, r), right->query(l, r));
  80.         return ret;
  81.     }
  82.  
  83.     ~segtree() {
  84.         if (left == nullptr) return;
  85.         delete left;
  86.         delete right;
  87.     }
  88. };
  89.  
  90. bool isPrime(int x) {
  91.     for (int i = 2; i * i <= x; i++) {
  92.         if (x % i == 0) return 0;
  93.     }
  94.     return x > 1;
  95. }
  96.  
  97.  
  98. int fpow(int a, int b, int mod) {
  99.     if (!b) return 1;
  100.     int ret = fpow(a, b >> 1, mod);
  101.     ret = fix(1ll * ret * ret, mod);
  102.     if (b & 1) ret = fix(1ll * ret * a, mod);
  103.     return ret;
  104. }
  105.  
  106. void init() {
  107.     static bool done = false;
  108.     if (done) return;
  109.     done = true;
  110.  
  111.     mt19937_64
  112.             rng(chrono::steady_clock::now().time_since_epoch().count());
  113.     uniform_int_distribution<int> dist(257, 10007);
  114.     do {
  115.         BASE = dist(rng);
  116.     } while (!isPrime(BASE));
  117.  
  118.     pw[0] = inv[0] = 1;
  119.     int iv1 = fpow(BASE, MOD - 2, MOD);
  120.     for (int i = 1; i < N; ++i) {
  121.         pw[i] = fix(1ll * pw[i - 1] * BASE, MOD);
  122.         inv[i] = fix(1ll * inv[i - 1] * iv1, MOD);
  123.     }
  124. }
  125.  
  126. struct Hash {
  127.     segtree* seg;
  128.     int n;
  129.     Hash(const string &s) {
  130.         n=sz(s);
  131.         init();
  132.         int H=0;
  133.         seg=new segtree(0,n);
  134.         for (int i = 0; i < n; i++) {
  135.             H=fix(0ll+H+1ll*s[i]*pw[i],MOD);
  136.             seg->update(i+1,i+1,H);
  137.         }
  138.     }
  139.  
  140.     int  getRange(int l, int r) const {
  141.         int p1=seg->query(r+1,r+1).val,p2=seg->query(l,l).val;
  142.         int H=fix(1ll*inv[l]*(p2-p1),MOD);
  143.         return H;
  144.     }
  145.     void update(int i,int val){
  146.         seg->update(i+1,seg->end,val);
  147.     }
  148. };
  149. int main() {
  150.     boAshraf
  151.     File();
  152.     int t = 1;
  153. //    cin>>t;
  154.     while (t--) {
  155.         sol();
  156.     }
  157.     return 0;
  158. }
  159.  
  160. void sol() {
  161.     int n,q;
  162.     cin>>n>>q;
  163.     vector<string>v(n);
  164.     vector<Hash>H1,H2;
  165.     for (int i = 0; i < n; ++i) {
  166.         string s;cin>>s;
  167.         v[i]=s;
  168.         Hash H(s);
  169.         H1.emplace_back(H);
  170.         reverse(all(s));
  171.         Hash HH(s);
  172.         H2.emplace_back(HH);
  173.     }
  174.     while(q--){
  175.         int op;cin>>op;
  176.         if(op==1){
  177.             int i,j;char c;
  178.             cin>>i>>j>>c;
  179.             i--;j--;
  180.             char last=v[i][j];
  181.             int diff=last-c;
  182.             int H=fix(1ll*pw[j]*diff,MOD);
  183.             H1[i].update(j,H);
  184.             int j2=sz(v[i])-j-1;
  185.             H=fix(1ll*pw[j2]*diff,MOD);
  186.             H2[i].update(j2,H);
  187.             v[i][j]=c;
  188.         }
  189.         else if(op==2){
  190.             int i,j,l1,r1,l2,r2;
  191.             cin>>i>>j>>l1>>r1>>l2>>r2;
  192.             i--,j--,l1--,r1--,l2--,r2--;
  193.             cout<<(H1[i].getRange(l1,r1)==H1[j].getRange(l2,r2)?"equal":"different")<<'\n';
  194.         }
  195.         else{
  196.             int i,j,l1,r1,l2,r2;
  197.             cin>>i>>j>>l1>>r1>>l2>>r2;
  198.             i--,j--,l1--,r1--,l2--,r2--;
  199.             int sz1=(r1-l1+1),sz2=(r2-l2+1);
  200.             int h1,h2;
  201.             int rev1,rev2;
  202.  
  203.             h1=H1[i].getRange(l1,r1),h2=H1[j].getRange(l2,r2);
  204.             l1=sz(v[i])-l1-1;r1=sz(v[i])-r1-1;l2=sz(v[j])-l2-1;r2=sz(v[j])-r2-1;
  205.             swap(l1,r1),swap(l2,r2);
  206.             rev1=H2[i].getRange(l1,r1),rev2=H2[j].getRange(l2,r2);
  207.  
  208.             int val1=fix(0ll+h1+1ll*pw[sz1]*h2,MOD);
  209.             int val2=fix(0ll+rev2+1ll*pw[sz2]*rev1,MOD);
  210.             cout<<(val1==val2?"cool":"not so cool")<<'\n';
  211.         }
  212.     }
  213. }
  214.  
  215. void File() {
  216. #ifndef ONLINE_JUDGE
  217.     freopen("input.txt", "r", stdin);
  218.     freopen("output.txt", "w", stdout);
  219. #endif
  220. }
  221.  
Advertisement
Add Comment
Please, Sign In to add comment