Advertisement
cosenza987

big day

May 18th, 2022
934
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.43 KB | None | 0 0
  1. //Слава Україні, Героям слава 🇺🇦
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6. using ull = unsigned long long;
  7.  
  8. template <int mod = (int)1e9 + 7> struct modint {
  9.     int x;
  10.     modint(int y = 0) : x((y% mod + mod) % mod) { }
  11.     friend modint operator ^ (modint a, long long b) {
  12.         modint r = 1;
  13.         for (; b; b >>= 1, a *= a) {
  14.             if (b & 1) {
  15.                 r *= a;
  16.             }
  17.         }
  18.         return r;
  19.     }
  20.     friend modint operator - (modint a) {
  21.         return modint(0) - a;
  22.     }
  23.     friend modint operator ! (modint a) {
  24.         return a ^ (mod - 2);
  25.     }
  26.     modint& operator /= (modint const& b) {
  27.         return *this *= !b;
  28.     }
  29.     friend modint operator + (modint a, modint const& b) {
  30.         return a += b;
  31.     }
  32.     friend modint operator - (modint a, modint const& b) {
  33.         return a -= b;
  34.     }
  35.     friend modint operator * (modint a, modint const& b) {
  36.         return a *= b;
  37.     }
  38.     friend modint operator / (modint a, modint const& b) {
  39.         return a /= b;
  40.     }
  41.     friend bool operator != (const modint& a, const modint b) {
  42.         return a.x != b.x;
  43.     }
  44.     friend bool operator == (const modint& a, const modint b) {
  45.         return a.x == b.x;
  46.     }
  47.     modint& operator *= (modint const& b) {
  48.         x = 1ll * x * b.x % mod;
  49.         return *this;
  50.     }
  51.     friend ostream& operator << (ostream& os, modint const& a) {
  52.         return os << a.x;
  53.     }
  54.     modint& operator += (modint const& b) {
  55.         x += b.x;
  56.         x = (x >= mod) ? x - mod : x;
  57.         return *this;
  58.     }
  59.     modint& operator -= (modint const& b) {
  60.         x = x >= b.x ? x - b.x : x - b.x + mod;
  61.         return *this;
  62.     }
  63. };
  64.  
  65. using mint = modint<>;
  66.  
  67. vector<mint> pr;
  68. const int prime = 1777771;
  69.  
  70. struct seg_hash {
  71.     int n;
  72.     string s;
  73.     vector<mint> st;
  74.     void build(int p, int l, int r) {
  75.         if(l == r) {
  76.             st[p] = static_cast<int>(s[l - 1]);
  77.             return;
  78.         }
  79.         int mid = (l + r) >> 1;
  80.         build(2 * p, l, mid);
  81.         build(2 * p + 1, mid + 1, r);
  82.         st[p] = st[2 * p] * pr[r - mid] + st[2 * p + 1];
  83.     }
  84.     void init(string s_) {
  85.         s = s_;
  86.         n = s_.size() + 1;
  87.         st.resize(4 * n);
  88.         n = s.size();
  89.         build(1, 1, n);
  90.     }
  91.     seg_hash() {}
  92.     mint query(int i, int j) {
  93.         return query(i, j, 1, 1, n);
  94.     }
  95.     mint query(int i, int j, int p, int l, int r) {
  96.         if(r < i or j < l) {
  97.             return 0;
  98.         }
  99.         if(i <= l and r <= j) {
  100.             return st[p];
  101.         }
  102.         int mid = (l + r) >> 1;
  103.         mint x = query(i, j, 2 * p, l, mid);
  104.         mint y = query(i, j, 2 * p + 1, mid + 1, r);
  105.         return x * pr[r - mid] + y;
  106.     }
  107.     void update(int x, int v) {
  108.         update(x, v, 1, 1, n);
  109.     }
  110.     void update(int x, int v, int p, int l, int r) {
  111.         if(x < l or r < x) {
  112.             return;
  113.         }
  114.         if(l == r and l == x) {
  115.             st[p] = v;
  116.             return;
  117.         }
  118.         int mid = (l + r) >> 1;
  119.         update(x, v, 2 * p, l, mid);
  120.         update(x, v, 2 * p + 1, mid + 1, r);
  121.         st[p] = st[2 * p] * pr[r - mid] + st[2 * p + 1];
  122.     }
  123. };
  124.  
  125. int main() {
  126.     ios_base::sync_with_stdio(false);
  127.     cin.tie(0);
  128.     pr.resize(200007);
  129.     pr[0] = 1;
  130.     for(int i = 1; i < 200007; i++) {
  131.         pr[i] = pr[i - 1] * prime;
  132.     }
  133.     int n, q;
  134.     cin >> n >> q;
  135.     vector<pair<seg_hash, seg_hash>> v(n + 1);
  136.     for(int i = 1; i <= n; i++) {
  137.         string s;
  138.         cin >> s;
  139.         v[i].first.init(s);
  140.         reverse(s.begin(), s.end());
  141.         v[i].second.init(s);
  142.     }
  143.     while(q--) {
  144.         int t;
  145.         cin >> t;
  146.         if(t == 1) {
  147.             int i, j;
  148.             char c;
  149.             cin >> i >> j >> c;
  150.             v[i].first.update(j, static_cast<int>(c));
  151.             v[i].second.update(v[i].second.n - j + 1, static_cast<int>(c));
  152.         } else if(t == 2) {
  153.             int i, j, l1, r1, l2, r2;
  154.             cin >> i >> j >> l1 >> r1 >> l2 >> r2;
  155.             mint a = v[i].first.query(l1, r1) * pr[l1 - 1];
  156.             mint b = v[j].first.query(l2, r2) * pr[l2 - 1];
  157.             int diff = abs(v[i].first.n - v[j].first.n);
  158.             if(v[i].first.n > v[j].first.n) {
  159.                 b *= pr[diff];
  160.             } else if(v[i].first.n < v[j].first.n) {
  161.                 a *= pr[diff];
  162.             }
  163.             cout << (a == b ? "equal\n" : "different\n");
  164.         } else {
  165.             int i, j, l1, r1, l2, r2;
  166.             cin >> i >> j >> l1 >> r1 >> l2 >> r2;
  167.             int diff = abs(v[i].first.n - v[j].first.n);
  168.             mint a, b, c, d;
  169.             a = v[i].first.query(l1, r1) * pr[l1 - 1];
  170.             b = v[i].second.query(v[i].second.n - r1 + 1, v[i].second.n - l1 + 1) * pr[v[i].second.n - r1];
  171.             c = v[j].first.query(l2, r2) * pr[l2 - 1];
  172.             d = v[j].second.query(v[j].second.n - r2 + 1, v[j].second.n - l2 + 1) * pr[v[j].second.n - r2];
  173.             if(v[i].first.n > v[j].first.n) {
  174.                 c *= pr[diff];
  175.                 d *= pr[diff];
  176.             } else if(v[i].first.n < v[j].first.n) {
  177.                 a *= pr[diff];
  178.                 b *= pr[diff];
  179.             }
  180.             a = (a * pr[r1 - l1 + 1] + c) * pr[r2 - l2 + 1];
  181.             d = (d * pr[r2 - l2 + 1] + b) * pr[r1 - l1 + 1];
  182.             cout << (a == d ? "cool\n" : "not so cool\n");
  183.         }
  184.     }
  185.     return 0;
  186. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement