#include <bits/stdc++.h> using namespace std; using ll = long long; #define thuhien "" #define re exit(0); const int maxn = 300009; int n,q; string s; bool state[maxn]; struct Fenwick2D { vector <int> index[maxn],fen[maxn]; void addevent(int x,int y) { for (;x <= 300003;x += (x & -x)) { index[x].push_back(y); } } void addevent(int x,int u,int y,int v) { addevent(x,y); addevent(x,v + 1); addevent(u + 1,y); addevent(u + 1,v + 1); } void build() { for (int i = 1;i <= 300003;i++) { sort(index[i].begin(),index[i].end()); index[i].resize(unique(index[i].begin(),index[i].end()) - index[i].begin()); fen[i].resize(index[i].size() + 2,0); } } int getpos(vector <int> & vt,int val) { return lower_bound(vt.begin(),vt.end(),val) - vt.begin() + 1; } void update(int x,int ori,int val) { for (;x <= 300003;x += (x & -x)) { for (int y = getpos(index[x],ori);y <= index[x].size();y += (y & -y)) { fen[x][y] += val; } } } void update(int x,int u,int y,int v,int val) { update(x,y,val); update(x,v + 1,-val); update(u + 1,y,-val); update(u + 1,v + 1,val); } int get(int x,int ori) { int ret = 0; for (;x;x -= (x & -x)) { for (int y = getpos(index[x],ori);y;y -= (y & -y)) { ret += fen[x][y]; } } return ret; } } fenwick; set <pair <int,int>> segment; struct qu { char op;int a,b; } query[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); if (fopen(thuhien".inp","r")) { freopen(thuhien".inp","r",stdin); freopen(thuhien".out","w",stdout); } cin >> n >> q >> s; s = " " + s; int last = -1; for (int i = 1;i <= n;i++) { state[i] = s[i] - '0'; if (s[i] == '0') { if (last != -1) segment.insert(make_pair(last,i - 1)); last = -1; } else { if (last == -1) last = i; } } if (last != -1) segment.insert(make_pair(last,n)); for (int i = 1;i <= q;i++) { string TMP;cin >> TMP >> query[i].a; query[i].op = TMP[0]; if (query[i].op == 'q') { cin >> query[i].b; query[i].b--; fenwick.addevent(query[i].a,query[i].b); } else { int pos = query[i].a; if (state[pos]) { auto it = segment.upper_bound(make_pair(pos,1e9)); it--; int l = it -> first,r = it -> second; fenwick.addevent(l,pos,pos,r); segment.erase(it); if (l < pos) segment.insert(make_pair(l,pos - 1)); if (r > pos) segment.insert(make_pair(pos + 1,r)); } else { int l = pos,r = pos; if (state[pos - 1]) { auto it = segment.upper_bound(make_pair(pos,-1)); it--; l = it -> first; segment.erase(it); } if (state[pos + 1]) { auto it = segment.lower_bound(make_pair(pos + 1,-1)); r = it -> second; segment.erase(it); } fenwick.addevent(l,pos,pos,r); segment.insert(make_pair(l,r)); } state[pos] ^= 1; } } fenwick.build(); segment.clear(); last = -1; for (int i = 1;i <= n;i++) { state[i] = s[i] - '0'; if (s[i] == '0') { if (last != -1) segment.insert(make_pair(last,i - 1)); last = -1; } else { if (last == -1) last = i; } } if (last != -1) segment.insert(make_pair(last,n)); for (int i = 1;i <= q;i++) { if (query[i].op == 'q') { int a = query[i].a,b = query[i].b; auto it = segment.upper_bound(make_pair(a,1e9)); if (it != segment.begin() && (--it) -> second >= b) { cout << fenwick.get(a,b) + i << '\n'; } else { // if (i == q) cout << "DCMM\n"; cout << fenwick.get(a,b) << '\n'; } } else { int pos = query[i].a; if (state[pos]) { auto it = segment.upper_bound(make_pair(pos,1e9)); it--; int l = it -> first,r = it -> second; fenwick.update(l,pos,pos,r,i); segment.erase(it); if (l < pos) segment.insert(make_pair(l,pos - 1)); if (r > pos) segment.insert(make_pair(pos + 1,r)); } else { int l = pos,r = pos; if (state[pos - 1]) { auto it = segment.upper_bound(make_pair(pos,-1)); it--; l = it -> first; segment.erase(it); } if (state[pos + 1]) { auto it = segment.lower_bound(make_pair(pos + 1,-1)); r = it -> second; segment.erase(it); } fenwick.update(l,pos,pos,r,-i); segment.insert(make_pair(l,r)); } state[pos] ^= 1; } } } /* Aiming: == +++++*** +:::::-=* ------= ========== ================== --:--== ============-- ========== ==-------=--:=--==== ---==++ ===========--====-= ==--======== ==--================= =:::-=+ ==============----==== ==:-========= ===:=== ======= =::--=+ ======== ==--==== ==--========== ==-:=== ======= -:::-:= ======= ======= ==--:== ======= ==--=== ======= =-:::-= ======= ======= =-.-=== ======= ==-==== ======= *:::----* ======= ======= ==--:== ======= ==-================== +-:::::-+ ====== ======= ==-:-=== ======= ==--================ *=-:::::-= ======= ======= ==---=============== ==--============= +--::---==* ====--= ======= ===--================= ==:-=== =:-::::--=+ ====-=== ======= ==.-=================== ==--=== =::::::---+ ====---== ========= ==---== ======= ======= +-:---=====+ ==-===--============== ======= ======= ======= =-:::::::--=+ =--=-============= ======== ======= ======= =--::::::--=+ ============= ***++++++++++***** */

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