Editorial for Bedao Regular Contest 15 - BITTEST
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Đặ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; }
Comments