/**
* APIO 2019 - Street Lamps
* Solution approach: Offline processing with CDQ Divide & Conquer
* Time Complexity: O(Q log^2 N)
*/
#include <bits/stdc++.h>
using namespace std;
// Define specific types for clarity
using ll = long long;
struct Query {
int type; // 0 for update, 1 for query
int x, y; // Coordinates (x = start of path, y = end of path - 1)
int val; // For update: value to add; For query: id of the query
int time; // Time of event
};
// Global variables
const int MAXN = 300005;
int n, q;
string s;
vector<Query> events;
ll ans[MAXN];
int bit[MAXN]; // Binary Indexed Tree (Fenwick Tree)
// BIT Operations
void update_bit(int idx, int val) {
for (; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
int query_bit(int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx)
sum += bit[idx];
return sum;
}
// CDQ Divide and Conquer
// Solves the 2D range sum problem by reducing one dimension (time)
void cdq(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
cdq(l, mid);
cdq(mid + 1, r);
// Merge step: Process interactions between Left (Updates) and Right (Queries)
// We sort both halves by X-coordinate to process efficienty
vector<Query> left_part, right_part;
for (int i = l; i <= mid; i++) {
if (events[i].type == 0) left_part.push_back(events[i]);
}
for (int i = mid + 1; i <= r; i++) {
if (events[i].type == 1) right_part.push_back(events[i]);
}
sort(left_part.begin(), left_part.end(), [](const Query& a, const Query& b) {
return a.x < b.x;
});
sort(right_part.begin(), right_part.end(), [](const Query& a, const Query& b) {
return a.x < b.x;
});
// Two-pointer sweep
int ptr = 0;
for (const auto& qry : right_part) {
while (ptr < left_part.size() && left_part[ptr].x <= qry.x) {
update_bit(left_part[ptr].y, left_part[ptr].val);
ptr++;
}
ans[qry.val] += query_bit(qry.y);
}
// Cleanup BIT for next steps (rollback changes)
for (int i = 0; i < ptr; i++) {
update_bit(left_part[i].y, -left_part[i].val);
}
}
// Helper to add a rectangle update
// Adds 'v' to rectangle [x1, x2] x [y1, y2]
// Uses difference array concept:
// (x1, y1) += v, (x1, y2+1) -= v, (x2+1, y1) -= v, (x2+1, y2+1) += v
void add_rectangle(int x1, int y1, int x2, int y2, int v, int t) {
if (x1 > x2 || y1 > y2) return;
events.push_back({0, x1, y1, v, t});
events.push_back({0, x1, y2 + 1, -v, t});
events.push_back({0, x2 + 1, y1, -v, t});
events.push_back({0, x2 + 1, y2 + 1, v, t});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
cin >> s;
// 1-based indexing for convenience
s = " " + s;
// Store active intervals of ON lamps
// Intervals are stored as {start, end}
set<pair<int, int>> intervals;
// Initialize intervals based on string s
for (int i = 1; i <= n; ++i) {
if (s[i] == '1') {
int j = i;
while (j <= n && s[j] == '1') j++;
intervals.insert({i, j - 1});
i = j - 1;
}
}
int query_count = 0;
for (int i = 1; i <= q; ++i) {
string type;
cin >> type;
if (type == "toggle") {
int idx;
cin >> idx;
int t = i;
if (s[idx] == '1') {
// Turning OFF
// Find the interval containing idx
auto it = intervals.upper_bound({idx, 1e9});
it--;
int L = it->first;
int R = it->second;
intervals.erase(it);
// Add positive time (Credit) to the rectangle that is breaking
// Rectangle: x in [L, idx], y in [idx, R]
// Query (a, b) maps to x=a, y=b-1.
// So valid queries are L <= a <= idx AND idx <= b-1 <= R
// => L <= a <= idx AND idx+1 <= b <= R+1
// Correct mapping: Query is (a, b). We map to (a, b-1).
// Range [L, R] supports query (a, b) if L <= a and b-1 <= R.
// The toggle breaks support for queries where a <= idx and b-1 >= idx.
// Bounds: a in [L, idx], b-1 in [idx, R]
add_rectangle(L, idx, idx, R, t, t);
// Insert split intervals
if (L <= idx - 1) intervals.insert({L, idx - 1});
if (idx + 1 <= R) intervals.insert({idx + 1, R});
s[idx] = '0';
} else {
// Turning ON
int L = idx, R = idx;
// Check if we can merge with left
auto it = intervals.lower_bound({idx, -1}); // first element >= idx
// Check right neighbor
if (it != intervals.end() && it->first == idx + 1) {
R = it->second;
it = intervals.erase(it); // Remove right, we will merge
}
// Check left neighbor
if (it != intervals.begin()) {
it--;
if (it->second == idx - 1) {
L = it->first;
intervals.erase(it);
}
}
intervals.insert({L, R});
// Subtract current time (Debit) from the new rectangle formed
// Bounds: a in [L, idx], b-1 in [idx, R]
add_rectangle(L, idx, idx, R, -t, t);
s[idx] = '1';
}
} else {
int a, b;
cin >> a >> b;
int t = i;
// Query map to (a, b-1)
int y = b - 1;
// 1. Add accumulated history from CDQ
events.push_back({1, a, y, query_count, t});
// 2. Check if currently valid (Active Asset)
// If valid, add current time 't' manually
auto it = intervals.upper_bound({a, 1e9});
bool active = false;
if (it != intervals.begin()) {
it--;
if (it->first <= a && it->second >= y) {
active = true;
}
}
if (active) {
ans[query_count] += t;
}
query_count++;
}
}
// Run CDQ
cdq(0, events.size() - 1);
for (int i = 0; i < query_count; i++) {
cout << ans[i] << "\n";
}
return 0;
}
