Đặt ~P_i=\sum_{j=1}^iS_j\times 10^{j}~ ~S[x..y] = S[z..t]\Leftrightarrow \frac{P_y-P_{x-1}}{10^x}=\frac{P_t-P_{z - 1}}{10^z}~

~\Rightarrow~ Ta sử dụng kĩ thuật Hashing.

Việc cần làm là duy trì ~P~ trên; ta dùng một cây phân đoạn (Segment Tree), mỗi node gồm 2 giá trị:

• ~sum=\sum S_j\times 10^j~
• ~psum = \sum (1-S_j)\times 10^j~

Việc đảo giá trị một đoạn chính là thao tác ~swap(sum, psum)~ Kết hợp với kĩ thuật lazy, ta có được lời giải cho bài toán

Code mẫu

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
const long long N = 2e5 + 5;
const long long base = 2;
const long long base2 = 3;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1e9 + 11;
ll pw[N], f[N], p[N], lazy[4 * N];
string s;

struct node {
  ll A, B, len;  

  void upd() {
    swap(A, B);
  }
} st[4 * N];

node add(node x, node y) {
  node ans;
  ans.A = (x.A * pw[y.len]+y.A)%MOD; 
  ans.B = (x.B * pw[y.len]+y.B)%MOD;
  ans.len = x.len + y.len;
  return ans;
};

ll getf(int l, int r) {
    return (f[r] - f[l - 1] * pw[r - l + 1] % MOD + MOD) % MOD;
}

ll getp(int l, int r) {
    return (p[r] - p[l - 1] * pw[r - l + 1] % MOD + MOD) % MOD;
}

void build(int id, int l, int r) {
    st[id] = {getf(l, r), getp(l, r), r - l + 1};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id] = add(st[id << 1], st[id << 1 | 1]);
}

void push(int id) {
    lazy[id] = 0;
    int u = id << 1, v = id << 1 | 1;
    lazy[u] ^= 1; lazy[v] ^= 1;
    st[u].upd(); st[v].upd();
}

void upd(int id, int l, int r, int lef, int rig) {
    // if (l == r) return;
    if (l > rig || r < lef) return;
    if (lef <= l && r <= rig) {
        lazy[id] ^= 1;
        st[id].upd();
        return;
    }

    if (lazy[id]) push(id);

    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, lef, rig);
    upd(id << 1 | 1, mid + 1, r, lef, rig);
    st[id] = add(st[id << 1], st[id << 1 | 1]);
}

node get(int id, int l, int r, int lef, int rig) {
    if (lef <= l && r <= rig) return st[id];
    // cout << l << ' ' << r << ' ' << lef << ' ' << rig << ": " << id << endl;
    if (lazy[id]) push(id);
    int mid = (l + r) >> 1;
    if (mid < lef) return get(id << 1 | 1, mid + 1, r, lef, rig);
    if (mid >= rig) return get(id << 1, l, mid, lef, rig);
    return add(get(id << 1, l, mid, lef, rig), get(id << 1 | 1, mid + 1, r, lef, rig));
}

ll q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("test.inp", "r", stdin);
    // freopen("test.out", "w", stdout);
    cin >> s;
    cin >> q;
    s = '#' + s;
    ll n = s.size() - 1;
    pw[0] = 1;

    rep(i, 1, n) {
        pw[i] = (pw[i - 1] * base) % MOD;
        f[i] = (f[i - 1] * base + s[i] - '0') % MOD;
        p[i] = (p[i - 1] * base + 1 - (s[i] - '0')) % MOD;
    }

    build(1, 1, n);

    int t, x, y, u, v;
    int cntNO = 0;
    int cntYES = 0;
    while (q --) {
        cin >> t >> x >> y;
        if (t == 1) {
            upd(1, 1, n, x, y);
            // cout << get(1, 1, n, x, y).A << '\n';
        }
        if (t == 2) {
            // cout << q << ": ";
            cin >> u >> v;
            // cout << x << ' ' << y << ' ' << u << ' ' << v << ": ";
            if (v - u != y - x) {
                cout << "NO\n";
                ++cntNO;
                continue;
            }
            // cout << get(1, 1, n, x, y).A << ' ' << get(1, 1, n, u, v).A << '_';
            string res = (get(1, 1, n, x, y).A == get(1, 1, n, u, v).A ? "YES" : "NO");
            cntYES += res == "YES";
            cntNO += res == "NO";
            cout << res << '\n';
        }
    }

    cerr << "Yes: " << cntYES << " - " << "No: " << cntNO;

    return 0;
}