#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,mmx,popcnt,tune=native"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Defines and one-liners
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
template <typename T> inline T& back(vector<T> &vec) { return *(vec.end() - 1); }
template <typename T> inline void pop(vector<T> &vec) { return vec.erase(vec.end() - 1); }
// Scan, Debug, and other nonsense
template <typename T> ostream& operator<<(ostream& out,vector<T> iter){out<<"[";for(auto t:iter){out<<t<<", ";}out<<"]";return out;}
template <typename T> void printArray(ostream& out,T* arr,int sz){out<<"[";for(int i=0;i<sz;i++){out<<arr[i]<<", "; } out<<"]";}
#define OUT_OPERATOR(type, propa, propb) ostream& operator<<(ostream& out,type obj){out<<"("<<#propa<<"="<<obj. propa<<", "<<#propb<<"="<<obj. propb<<")";return out;}
void scan(){}
template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
int di_; string dnms_, co_ = ",";
void debug_(){cout<<endl;}
template<typename F, typename... R> void debug_(F f,R... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
#define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)
// Structures for Problem
struct seg {
int l, r;
bool operator<(const seg &o) const {
return l < o.l;
}
bool operator==(const seg &o) const {
return l == o.l && r == o.r;
}
};
struct line {
int m, b;
void merge(line o) {
m += o.m;
b += o.b;
}
void inv() {
m *= -1;
b *= -1;
}
int gety(int x) {
return m * x + b;
}
};
OUT_OPERATOR(seg, l, r)
OUT_OPERATOR(line, m, b)
const line ZERO = {0, 0};
inline line mergel(line a, line b) {
a.merge(b);
return a;
}
inline line invl(line a) {
a.inv();
return a;
}
// Segment Tree
struct InnerSegNode {
int l, r; line v;
};
const int MSN = 20e6 + 1;
InnerSegNode nodes[MSN];
inline int make() {
static int ctr = 0;
// assert(ctr + 1 < MSN);
return ++ctr;
}
#define nrt nodes[rt] // Current node
int cqr; line cv; // Current QL and QR
line upd(int &rt, int l, int r) {
if (!rt) rt = make();
if (l > cqr || r < cqr) return nrt.v;
if (l == cqr && r == cqr) {
nrt.v.merge(cv);
return nrt.v;
}
int mid = (l + r) >> 1;
return nrt.v = mergel(upd(nrt.l, l, mid), upd(nrt.r, mid + 1, r));
}
line query(int &rt, int l, int r) {
if (!rt || l > cqr) return ZERO;
if (r <= cqr) return nrt.v;
int mid = (l + r) >> 1;
return mergel(query(nrt.l, l, mid), query(nrt.r, mid + 1, r));
}
#undef nrt
const int MN = 3e5 + 1;
int n, q, ba, bb;
string bt;
bool state[MN];
set<seg> segs;
// BIT Functions
int bit[MN]; // Bit of "SegTree"
inline line sum(int a, int b) {
cqr = b;
line ret = ZERO;
for (; a; a -= a & -a)
ret.merge(query(bit[a], 1, n));
return ret;
}
inline void add(int a) {
for(; a <= n; a += a & -a) {
upd(bit[a], 1, n);
}
}
// Range Add/Sub functions and other utility functions used in main()
inline void updRect(int x1, int y1, int x2, int y2, const line x) {
cv = x;
cqr = y1; add(x1);
cqr = y2 + 1; add(x2 + 1);
cv.inv();
add(x1); // cqr already y2 + 1
cqr = y1; add(x2 + 1);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
scan(n, q, bt);
// Init hashmaps and set states
for (int i = 1; i <= n; i++)
state[i] = bt[i - 1] == '1';
// for (int i = 1; i <= n; i++) {
// bit[i].reserve(128);
// bit[i].max_load_factor(0.25);
// }
// Initial states
int lastBegin = -1;
for (int i = 1; i <= n; i++) {
if (state[i] && lastBegin == -1)
lastBegin = i;
else if (!state[i] && lastBegin != -1) {
segs.insert({lastBegin, i - 1});
lastBegin = -1;
}
}
if (lastBegin != -1)
segs.insert({lastBegin, n});
// Add states onto 2D BIT
for (auto seg : segs)
updRect(seg.l, seg.l, seg.r, seg.r, {1, 0});
for (int i = 0; i < q; i++) {
// CurTime = i + 1
scan(bt, ba);
// Debug
// vector<seg> vss(segs.begin(), segs.end());
// debug(i, vss);
// for (int j = 1; j <= n; j++) {
// vector<int> vc;
// for (int k = 1; k <= n; k++) {
// auto sumv = sum(j, k);
// // debug(j, k, sumv, sumv.gety(i + 1));
// vc.push_back(sumv.gety(i + 1));
// }
// debug(vc);
// }
if (bt == "query") {
scan(bb);
bb--;
cout << sum(ba, bb).gety(i + 1) << "\n";
}
else { // bt == "toggle"
if (state[ba]) {
// Find state to split
auto ptr = --segs.upper_bound({ba, -1});
// There should always be an L who is less than the current thing
updRect(ptr->l, ba, ba, ptr->r, {-1, i + 1});
segs.erase(ptr);
seg ins1 = {ptr->l, ba - 1}, ins2 = {ba + 1, ptr->r};
if (ins1.l <= ins1.r) // if ins1.l > ins1.r then the seg is size 0 and doesn't matter
segs.insert(ins1);
if (ins2.l <= ins2.r) // Same for ins2
segs.insert(ins2);
}
else { // !state[ba]
// Find states to combine
auto ptr2 = segs.upper_bound({ba, -1}), ptr = ptr2; // ptr = left, ptr2 = right
// ptr is invalid -> ptr2 == segs.begin(), ptr2 s invalid, ptr2 == segs.end()
bool condPtr = false, condPtr2 = false;
if (segs.size()) { // If the segs set is empty, don't try to set the ptr
ptr--; //
condPtr = (ptr2 != segs.begin()) && (ptr->r + 1 == ba);
condPtr2 = (ptr2 != segs.end()) && (ptr2->l - 1 == ba);
}
int l = condPtr ? ptr->l : ba, r = condPtr2 ? ptr2->r : ba;
updRect(l, ba, ba, r, {1, -i - 1});
// debug(i, ba, condPtr, condPtr2, l, r);
if (condPtr)
segs.erase(ptr);
if (condPtr2)
segs.erase(ptr2);
segs.insert({l, r});
}
state[ba] ^= true;
}
}
return 0;
}
