#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <array>
#include <set>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define pb push_back
#define all(x) x.begin(),x.end()
template<typename T>
struct fen {
vector<T> tr;
ll mxn;
fen(ll sz) {
mxn = sz;
tr.assign(sz + 5, 0);
}
void upd(ll g, T k) {
g++;
assert(g > 0);
for (; g <= mxn; g += g&-g)
tr[g] += k;
}
T ge(ll g) {
g++;
T res = 0;
for (; g > 0; g -= g&-g)
res += tr[g];
return res;
}
T rng(ll l, ll r) {
if (l > r) return T(0);
return ge(r) - ge(l - 1);
}
};
void solve() {
ll n, q; cin >> n >> q;
string input_string; cin >> input_string;
vector<ll> a(n);
for (int i = 0; i < n; i++) a[i] = input_string[i] - '0';
// x, y, delta, idx, multiplier
using query_t = array<ll, 5>;
ll chain = 0;
set<pii> gang;
for (int i = 0; i < n; i++) {
if (a[i]) { chain++; }
else {
if (chain) {
gang.insert({i - chain, i - 1});
}
chain = 0;
}
}
if (chain) gang.insert({n - chain, n - 1});
vector<query_t> queries;
for (const auto& [x, y] : gang) {
queries.pb({x, y, 0, -1, 1});
}
constexpr ll INF = 1e18;
for (int q_idx = 1; q_idx <= q; q_idx++) {
string s; cin >> s;
if (s == "query") {
ll l, r;
cin >> l >> r;
l--; r--; r--;
// start < l + 1, end > r - 1
queries.pb({l + 1, r - 1, -1, q_idx, 1});
} else {
ll x; cin >> x; x--;
if (a[x] == 1) {
// splitttter
auto geq = gang.lower_bound({x, -INF});
if ((*geq).first != x) {
assert(geq != gang.begin());
geq = prev(geq);
}
auto [l, r] = *geq; gang.erase(geq);
assert(l <= x and r >= x);
queries.pb({l, r, q_idx, -1, -1});
if (l < x) {
gang.insert({l, x - 1});
queries.pb({l, x - 1, q_idx, -1, 1});
}
if (r > x) {
gang.insert({x + 1, r});
queries.pb({x + 1, r, q_idx, -1, 1});
}
} else {
// uniter!
ll l_under = -1, r_under = -1, l_above = -1, r_above = -1;
if (x > 0 and a[x - 1] == 1) {
auto iter = prev(gang.lower_bound({x, x}));
l_under = (*iter).first, r_under = (*iter).second;
assert(l_under < x and r_under < x and l_under <= r_under);
queries.pb({l_under, r_under, q_idx, -1, -1});
gang.erase(iter);
}
if (x < n - 1 and a[x + 1] == 1) {
auto iter = gang.lower_bound({x, x});
assert(iter != gang.end());
l_above = (*iter).first, r_above = (*iter).second;
assert(l_above > x and r_above > x and l_above <= r_above);
queries.pb({l_above, r_above, q_idx, -1, -1});
gang.erase(iter);
}
ll new_l = x, new_r = x;
if (l_under != -1) new_l = l_under;
if (r_above != -1) new_r = r_above;
gang.insert({new_l, new_r});
queries.pb({new_l, new_r, q_idx, -1, 1});
}
a[x] ^= 1;
}
#ifdef LOCAL
cout << "current gang: \n";
for (auto& [x, y] : gang) {
cout << x << " " << y << "\n";
}
#endif
}
vector<bool> v(q + 1);
vector<ll> ans(q + 1);
fen<ll> tree_pos(n), tree_neg(n);
fen<ll> tree_count(n);
#ifdef LOCAL
cout << "current gang: \n";
for (auto& [x, y] : gang) {
cout << x << " " << y << "\n";
}
cout << "queries: \n";
for (auto& [l, r, delta, idx, multiplier] : queries)
cout << l << " " << r << ' ' << delta << ' ' << idx << ' ' << multiplier << "\n";
#endif
auto dfs = [&](auto& dfs, ll l, ll r) -> void {
if (l == r) return;
ll m = (l + r) / 2;
dfs(dfs, l, m);
dfs(dfs, m + 1, r);
vector<ll> l_idx(m - l + 1), r_idx(r - m);
iota(all(l_idx), l); iota(all(r_idx), m + 1);
sort(all(l_idx), [&](ll i, ll j) {
return queries[i] < queries[j];
});
sort(all(r_idx), [&](ll i, ll j) {
return queries[i] < queries[j];
});
ll next_left_ptr = 0;
vector<array<ll, 3>> upds;
for (const auto& q_idx : r_idx) {
const auto& [l, r, delta, idx, multiplier] = queries[q_idx];
while (next_left_ptr < (int)l_idx.size()) {
const auto& o = l_idx[next_left_ptr];
if (queries[o][0] >= l) break;
const auto [px, py, pdelta, pidx, pmult] = queries[o];
if (pidx == -1) {
assert(pdelta != -1);
if (pmult == -1) {
tree_neg.upd(py, pdelta);
tree_count.upd(py, -1);
} else {
tree_pos.upd(py, pdelta);
tree_count.upd(py, 1);
}
upds.pb({py, pdelta, pmult});
}
next_left_ptr++;
}
// with r greater
if (idx != -1) {
assert(delta == -1);
ll from_count = idx * tree_count.rng(r + 1, n - 1);
#ifdef LOCAL
cout << idx << " " << from_count << '\n';
#endif
ll res = from_count - tree_pos.rng(r + 1, n - 1) + tree_neg.rng(r + 1, n - 1);
ans[idx] += res;
v[idx] = true;
}
}
for (auto& [idx, delta, mult] : upds) {
if (mult == -1) {
tree_neg.upd(idx, -delta);
tree_count.upd(idx, 1);
} else {
tree_pos.upd(idx, -delta);
tree_count.upd(idx, -1);
}
}
};
dfs(dfs, 0, (int)queries.size() - 1);
for (int i = 1; i <= q; i++) if (v[i]) {
cout << ans[i] << '\n';
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
solve();
return 0;
}
