/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 3e5 + 10;
struct BIT
{
vector < int > ip[maxn], bit[maxn];
void init()
{
for (int i = 0; i < maxn; i ++)
{
ip[i].push_back(0);
sort(ip[i].begin(), ip[i].end());
ip[i].resize(unique(ip[i].begin(), ip[i].end()) - ip[i].begin());
bit[i].resize(ip[i].size());
}
}
void add_init(int x, int y)
{
for (int i = x; i < maxn; i += (i & -i))
ip[i].push_back(y);
}
void add(int x, int y, int v)
{
///cout << "start" << endl;
for (int i = x; i < maxn; i += (i & -i))
{
///cout << ip[i][0] << endl;
int y2 = lower_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin();
for (int j = y2; j < bit[i].size(); j += (j & -j))
bit[i][j] += v;
}
/// cout << "fine" << endl;
}
int query(int x, int y)
{
int ret = 0;
for (int i = x; i > 0; i -= (i & -i))
{
int y2 = upper_bound(ip[i].begin(), ip[i].end(), y) - ip[i].begin() - 1;
for (int j = y2; j > 0; j -= (j & -j))
{
///cout << bit[i][j] << endl;
ret = ret + bit[i][j];
}
}
return ret;
}
} bit;
struct interval
{
int left, right, in_time;
interval(int _left = 0, int _right = 0, int _in_time = 0)
{
left = _left;
right = _right;
in_time = _in_time;
}
bool operator < (const interval &it) const
{
if (left == it.left)
{
if (right == it.right)
return in_time < it.in_time;
return right < it.right;
}
return left < it.left;
}
};
struct base_query
{
string type;
int x, a, b;
} base_ask[maxn];
int n, q, add_ans[maxn];
char c[maxn], cs[maxn];
void input()
{
cin >> n >> q;
n ++;
for (int i = 1; i < n; i ++)
cin >> c[i], cs[i] = c[i];
for (int i = 1; i <= q; i ++)
{
cin >> base_ask[i].type;
if (base_ask[i].type == "query")
{
cin >> base_ask[i].a >> base_ask[i].b;
}
else
{
cin >> base_ask[i].x;
}
}
}
set < pair < int, int > > available;
interval bef1[maxn], aft1[maxn], cur1[maxn];
void create_intervals()
{
set < interval > st;
int beg = 1;
for (int i = 1; i < n; i ++)
{
if (c[i] == '0')
{
///cout << beg << " -- " << i << endl;
st.insert(interval(beg, i, 0));
available.insert({beg, i});
beg = i + 1;
}
}
st.insert(interval(beg, n, 0));
available.insert({beg, n});
for (int i = 1; i <= q; i ++)
{
if (base_ask[i].type == "toggle")
{
int pos = base_ask[i].x;
if (c[pos] == '0')
{
c[pos] = '1';
set < interval > :: iterator aft_it = st.lower_bound(interval(pos + 1, pos + 1, -1));
set < interval > :: iterator bef_it = prev(aft_it);
interval bef = *bef_it;
interval aft = *aft_it;
interval cur(bef.left, aft.right, i);
st.erase(bef);
st.erase(aft);
st.insert(cur);
bef1[i] = bef;
aft1[i] = aft;
cur1[i] = cur;
available.insert({cur.left, cur.right});
}
else
{
c[pos] = '0';
set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
interval cur = *cur_it;
interval bef(cur.left, pos, i);
interval aft(pos + 1, cur.right, i);
st.erase(cur);
st.insert(bef);
st.insert(aft);
bef1[i] = bef;
aft1[i] = aft;
cur1[i] = cur;
available.insert({bef.left, bef.right});
available.insert({aft.left, aft.right});
}
}
else
{
int pos = base_ask[i].a;
set < interval > :: iterator cur_it = prev(st.upper_bound(interval(pos, n + 1, -1)));
if (cur_it -> right >= base_ask[i].b)
add_ans[i] = i - cur_it -> in_time;
}
}
//for (pair < int, int > cur : available)
// cout << cur.first << " : " << cur.second << endl;
}
unordered_map < int, int > act[maxn], act_time[maxn];
void update_interval(interval cur, int cur_time)
{
if (cur.left == cur.right)
return;
///cout << "update " << cur.left << " " << cur.right << endl;
if (act[cur.left][cur.right])
{
act[cur.left][cur.right] = 0;
bit.add(cur.left, cur.right, cur_time - act_time[cur.left][cur.right]);
}
else
{
act_time[cur.left][cur.right] = cur_time;
act[cur.left][cur.right] = 1;
}
}
void build_trees()
{
for (pair < int, int > cur : available)
{
if (cur.first != cur.second)
{
bit.add_init(cur.first, cur.second);
}
}
bit.init();
}
int query(int a, int b)
{
return bit.query(a, n) - bit.query(a, b - 1);
}
void simulate()
{
int beg = 1;
for (int i = 1; i < n; i ++)
{
c[i] = cs[i];
if (c[i] == '0')
{
update_interval(interval(beg, i, -1), 0);
beg = i + 1;
}
}
update_interval(interval(beg, n, -1), 0);
///cout << "--------------" << endl;
for (int i = 1; i <= q; i ++)
{
if (base_ask[i].type == "toggle")
{
///cout << "toggle" << endl;
int pos = base_ask[i].x;
if (c[pos] == '0')
{
c[pos] = '1';
interval bef = bef1[i];
interval aft = aft1[i];
interval cur = cur1[i];
update_interval(bef, i);
update_interval(aft, i);
update_interval(cur, i);
}
else
{
c[pos] = '0';
///set < interval > :: iterator cur_it = prev(st.lower_bound(interval(pos + 1, pos + 1, -1)));
interval cur = cur1[i];
interval bef = bef1[i];
interval aft = aft1[i];
update_interval(bef, i);
update_interval(aft, i);
update_interval(cur, i);
}
}
else
{
int ans = query(base_ask[i].a, base_ask[i].b);
cout << ans + add_ans[i] << endl;
}
}
//for (pair < int, int > cur : available)
// cout << cur.first << " : " << cur.second << endl;
}
void solve()
{
input();
create_intervals();
build_trees();
simulate();
}
int main()
{
solve();
return 0;
}
