#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll, ll> #define fi first #define se second #define orz ios::sync_with_stdio(0); cin.tie(0); const ll N = 5e5 + 5; struct query { ll t, x, y, val; }; bool cmp(query A, query B) { return A.t < B.t; } bool cmpY(query A, query B) { return A.y > B.y; } ll n; ll a[N]; ll lst[N], res[N]; vector<query> ok; vector<ll> posQ; struct Fenwick { ll bit[N]; void reset() { for (ll i = 1; i < N; i++) bit[i] = 0; } void upd(ll i, ll v) { for (; i < N; i += i & -i) bit[i] += v; } ll getP(ll i) { ll s = 0; for (; i; i -= i & -i) s += bit[i]; return s; } ll find(ll k) { ll l = 1, r = n + 2, ans = n + 2; while (l <= r) { ll m = (l + r) >> 1; if (getP(m) >= k) ans = m, r = m - 1; else l = m + 1; } return ans; } }; Fenwick Tz, T1, T2; void cdq(ll l, ll r) { if (l == r) return; ll m = (l + r) >> 1; cdq(l, m); cdq(m + 1, r); vector<query> upd, que, reset; for (ll i = l; i <= m; i++) if (ok[i].val != 0) upd.push_back(ok[i]); for (ll i = m + 1; i <= r; i++) if (ok[i].val == 0) que.push_back(ok[i]); sort(upd.begin(), upd.end(), cmpY); sort(que.begin(), que.end(), cmpY); ll i = 0, j = 0; while (i < (ll)upd.size() && j < (ll)que.size()) { if (upd[i].y >= que[j].y) { T1.upd(upd[i].x + 1, upd[i].val); T2.upd(upd[i].x + 1, upd[i].val * upd[i].t); reset.push_back(upd[i++]); } else { res[que[j].t] += que[j].t * T1.getP(que[j].x + 1) - T2.getP(que[j].x + 1); j++; } } while (j < (ll)que.size()) { res[que[j].t] += que[j].t * T1.getP(que[j].x + 1) - T2.getP(que[j].x + 1); j++; } for (auto &v : reset) { T1.upd(v.x + 1, -v.val); T2.upd(v.x + 1, -v.val * v.t); } } signed main() { orz if (fopen(".inp", "r")) { freopen(".inp", "r", stdin); freopen(".out", "w", stdout); } ll q; cin >> n >> q; for (ll i = 1; i <= n; i++) { char c; cin >> c; a[i] = (c == '1'); } Tz.upd(1, 1); Tz.upd(n + 2, 1); for (ll i = 1; i <= n; i++) if (!a[i]) Tz.upd(i + 1, 1); ll lim = Tz.getP(n + 2); ll last = Tz.find(1) - 1; for (ll i = 2; i <= lim; i++) { ll cur = Tz.find(i) - 1; ok.push_back({0, last, cur, 1}); last = cur; } for (ll i = 1; i <= q; i++) { string t; cin >> t; if (t == "query") { ll x, y; cin >> x >> y; posQ.push_back(i); ok.push_back({i, x - 1, y, 0}); } else { ll x; cin >> x; if (!a[x]) { ll c = Tz.getP(x + 1); ll l = Tz.find(c - 1) - 1; ll r = Tz.find(c + 1) - 1; ok.push_back({i, l, x, -1}); ok.push_back({i, x, r, -1}); ok.push_back({i, l, r, 1}); Tz.upd(x + 1, -1); a[x] = 1; } else { ll c = Tz.getP(x + 1); ll l = Tz.find(c) - 1; ll r = Tz.find(c + 1) - 1; ok.push_back({i, l, r, -1}); ok.push_back({i, l, x, 1}); ok.push_back({i, x, r, 1}); Tz.upd(x + 1, 1); a[x] = 0; } } } sort(ok.begin(), ok.end(), cmp); cdq(0, (ll)ok.size() - 1); for (ll id : posQ) cout << res[id] << '\n'; return 0; }

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~