Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
- #define ll long long
- #define ld long double
- #define sz(s) (int)(s).size()
- #define all(s) (s).begin(),(s).end()
- #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
- using namespace __gnu_pbds;
- using namespace std;
- void File();
- void sol();
- struct Node {
- int val = 0, lazy = 0;
- } neutral;
- const int N = 2e5 + 5, MOD = 1e9 + 7;
- int pw[N], inv[N], BASE;
- int fix(ll x, int mod) {
- x %= mod;
- if (x < 0) x += mod;
- return x;
- }
- struct segtree {
- segtree *left = nullptr, *right = nullptr;
- Node node = {};
- int start, end;
- segtree(int l = 0, int r = 0) : start(l), end(r) {}
- void extend() {
- if (left == nullptr) {
- int mid = (start + end) >> 1;
- left = new segtree(start, mid);
- right = new segtree(mid + 1, end);
- }
- }
- Node pushup(Node a, Node b) {
- Node ret;
- ret.val = fix(0ll+a.val + b.val,MOD);
- return ret;
- }
- void pushdown() {
- node.val =fix(0ll+node.val+node.lazy,MOD);
- if (start != end) {
- extend();
- left->node.lazy =fix(left->node.lazy+node.lazy,MOD);
- right->node.lazy =fix(right->node.lazy+node.lazy,MOD);
- }
- node.lazy = 0;
- }
- void update(int l, int r, int val) {
- pushdown();
- if (start > r || end < l) return;
- if (start >= l && end <= r) {
- node.lazy = val;
- pushdown();
- return;
- }
- extend();
- left->update(l, r, val);
- right->update(l, r, val);
- node = pushup(left->node, right->node);
- }
- Node query(int l, int r) {
- pushdown();
- if (r < start || end < l) return neutral;
- if (l <= start && end <= r) return node;
- extend();
- Node ret = pushup(left->query(l, r), right->query(l, r));
- return ret;
- }
- ~segtree() {
- if (left == nullptr) return;
- delete left;
- delete right;
- }
- };
- bool isPrime(int x) {
- for (int i = 2; i * i <= x; i++) {
- if (x % i == 0) return 0;
- }
- return x > 1;
- }
- int fpow(int a, int b, int mod) {
- if (!b) return 1;
- int ret = fpow(a, b >> 1, mod);
- ret = fix(1ll * ret * ret, mod);
- if (b & 1) ret = fix(1ll * ret * a, mod);
- return ret;
- }
- void init() {
- static bool done = false;
- if (done) return;
- done = true;
- mt19937_64
- rng(chrono::steady_clock::now().time_since_epoch().count());
- uniform_int_distribution<int> dist(257, 10007);
- do {
- BASE = dist(rng);
- } while (!isPrime(BASE));
- pw[0] = inv[0] = 1;
- int iv1 = fpow(BASE, MOD - 2, MOD);
- for (int i = 1; i < N; ++i) {
- pw[i] = fix(1ll * pw[i - 1] * BASE, MOD);
- inv[i] = fix(1ll * inv[i - 1] * iv1, MOD);
- }
- }
- struct Hash {
- segtree* seg;
- int n;
- Hash(const string &s) {
- n=sz(s);
- init();
- int H=0;
- seg=new segtree(0,n);
- for (int i = 0; i < n; i++) {
- H=fix(0ll+H+1ll*s[i]*pw[i],MOD);
- seg->update(i+1,i+1,H);
- }
- }
- int getRange(int l, int r) const {
- int p1=seg->query(r+1,r+1).val,p2=seg->query(l,l).val;
- int H=fix(1ll*inv[l]*(p2-p1),MOD);
- return H;
- }
- void update(int i,int val){
- seg->update(i+1,seg->end,val);
- }
- };
- int main() {
- boAshraf
- File();
- int t = 1;
- // cin>>t;
- while (t--) {
- sol();
- }
- return 0;
- }
- void sol() {
- int n,q;
- cin>>n>>q;
- vector<string>v(n);
- vector<Hash>H1,H2;
- for (int i = 0; i < n; ++i) {
- string s;cin>>s;
- v[i]=s;
- Hash H(s);
- H1.emplace_back(H);
- reverse(all(s));
- Hash HH(s);
- H2.emplace_back(HH);
- }
- while(q--){
- int op;cin>>op;
- if(op==1){
- int i,j;char c;
- cin>>i>>j>>c;
- i--;j--;
- char last=v[i][j];
- int diff=last-c;
- int H=fix(1ll*pw[j]*diff,MOD);
- H1[i].update(j,H);
- int j2=sz(v[i])-j-1;
- H=fix(1ll*pw[j2]*diff,MOD);
- H2[i].update(j2,H);
- v[i][j]=c;
- }
- else if(op==2){
- int i,j,l1,r1,l2,r2;
- cin>>i>>j>>l1>>r1>>l2>>r2;
- i--,j--,l1--,r1--,l2--,r2--;
- cout<<(H1[i].getRange(l1,r1)==H1[j].getRange(l2,r2)?"equal":"different")<<'\n';
- }
- else{
- int i,j,l1,r1,l2,r2;
- cin>>i>>j>>l1>>r1>>l2>>r2;
- i--,j--,l1--,r1--,l2--,r2--;
- int sz1=(r1-l1+1),sz2=(r2-l2+1);
- int h1,h2;
- int rev1,rev2;
- h1=H1[i].getRange(l1,r1),h2=H1[j].getRange(l2,r2);
- l1=sz(v[i])-l1-1;r1=sz(v[i])-r1-1;l2=sz(v[j])-l2-1;r2=sz(v[j])-r2-1;
- swap(l1,r1),swap(l2,r2);
- rev1=H2[i].getRange(l1,r1),rev2=H2[j].getRange(l2,r2);
- int val1=fix(0ll+h1+1ll*pw[sz1]*h2,MOD);
- int val2=fix(0ll+rev2+1ll*pw[sz2]*rev1,MOD);
- cout<<(val1==val2?"cool":"not so cool")<<'\n';
- }
- }
- }
- void File() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
Advertisement
Add Comment
Please, Sign In to add comment