#include <bits/stdc++.h> /* Checklist: - Check statement: - Check filename: - Check test limit: - Stresstest: */ using namespace std; using ll = long long; #define int long long #define pii pair<ll, ll> #define fi first #define se second const ll N = 5e5 + 5; struct query { int 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; } int n; int a[N]; int lst[N], res[N]; vector<query> ok; vector<int> posQ; struct Fenwick { int bit[N]; void reset() { for (int i = 1; i < N; i++) bit[i] = 0; } void upd(int i, int v) { for (; i < N; i += i & -i) bit[i] += v; } int getP(int i) { int s = 0; for (; i; i -= i & -i) s += bit[i]; return s; } int find(int k) { int l = 1, r = n + 2, ans = n + 2; while (l <= r) { int 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(int l, int r) { if (l == r) return; int m = (l + r) >> 1; cdq(l, m); cdq(m + 1, r); vector<query> upd, que, reset; for (int i = l; i <= m; i++) if (ok[i].val != 0) upd.push_back(ok[i]); for (int 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); int i = 0, j = 0; while (i < (int)upd.size() && j < (int)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 < (int)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() { ios::sync_with_stdio(false); cin.tie(0); if (fopen(".inp", "r")) { freopen(".inp", "r", stdin); freopen(".out", "w", stdout); } int q; cin >> n >> q; for (int i = 1; i <= n; i++) { char c; cin >> c; a[i] = (c == '1'); } Tz.upd(1, 1); Tz.upd(n + 2, 1); for (int i = 1; i <= n; i++) if (!a[i]) Tz.upd(i + 1, 1); int lim = Tz.getP(n + 2); int last = Tz.find(1) - 1; for (int i = 2; i <= lim; i++) { int cur = Tz.find(i) - 1; ok.push_back({0, last, cur, 1}); last = cur; } for (int i = 1; i <= q; i++) { string t; cin >> t; if (t == "query") { int x, y; cin >> x >> y; posQ.push_back(i); ok.push_back({i, x - 1, y, 0}); } else { int x; cin >> x; if (!a[x]) { int c = Tz.getP(x + 1); int l = Tz.find(c - 1) - 1; int 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 { int c = Tz.getP(x + 1); int l = Tz.find(c) - 1; int 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, (int)ok.size() - 1); for (int id : posQ) cout << res[id] << '\n'; return 0; }

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