#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define eb emplace_back
#define mp make_pair
typedef pair<int,int> pii;
#define f first
#define s second
#ifdef local
#define debug(x,label) cerr<<"DEBUG "<<label<<" "<<x<<'\n';
#else
#define debug(x,label);
#endif
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a>b)?a:b)
typedef cc_hash_table<int, int, hash<int>> ht;
//const int mod=1000000007 or 998244353;
int n,q;
ht ft[300005];
#define ls(x) (x&(-x))
void update(int a,int b,int upd){b++;
//cout<<a<<' '<<b<<' '<<upd<<" UPDATE\n";
for(;a<=n;a+=ls(a)){
for(int x=b;x<=n;x+=ls(x)){
if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
else ft[a][x]+=upd;
}
}
}
int query(int a,int b){b++;
int ans=0;
for(;a;a-=ls(a)){
for(int x=b;x;x-=ls(x)){
//if(ft[a].find(x)==ft[a].end())continue;
ans+=ft[a][x];
}
}
return ans;
}
bool lam[300005];
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int prev=0,ans,a,b,c,d;
cin>>n>>q;
string s;
cin>>s;
set<pair<pii,int> > cur;//"cur ranges"
set<pair<pii,int> >::iterator it;
for(int i=0;i<n;i++){
if(s[i]=='0'){
if(prev<=i-1){
cur.insert(mp(mp(prev+1,i),0));
}
prev=i+1;
}
lam[i+1]=(s[i]=='1');
}
if(prev<=n-1){
cur.insert(mp(mp(prev+1,n),0));
}
for(int i=1;i<=q;i++){
cin>>s;
if(s[0]=='t'){
cin>>a;
if(lam[a]){
it=--cur.upper_bound(mp(mp(a,INT_MAX),-1));
b=it->f.f;c=it->f.s;//range b to c...
update(b,n-c,i-it->s);
cur.erase(it);
if(b<a)cur.insert(mp(mp(b,a-1),i));
if(a<c)cur.insert(mp(mp(a+1,c),i));
}else{
b=c=a;
if(lam[a-1]){
it=--cur.upper_bound(mp(mp(a-1,INT_MAX),-1));
b=it->f.f;
update(it->f.f,n-it->f.s,i-it->s);
cur.erase(it);
}
if(lam[a+1]){
it=--cur.upper_bound(mp(mp(a+1,INT_MAX),-1));
c=it->f.s;
update(it->f.f,n-it->f.s,i-it->s);
cur.erase(it);
}
cur.insert(mp(mp(b,c),i));
}
lam[a]^=1;
}else{
ans=0;
cin>>a>>b;b--;
it=cur.upper_bound(mp(mp(a,INT_MAX),-1));
if(it!=cur.begin()){
it--;
if(it->f.f<=a && b<=it->f.s){
ans+=(i-it->s);
}
}
ans+=query(a,n-b);//if first index >=a, then n-first index<=n-a
cout<<ans<<'\n';
}
}
return 0;
}
/*
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/
Compilation message
street_lamps.cpp:19:9: error: 'cc_hash_table' does not name a type
19 | typedef cc_hash_table<int, int, hash<int>> ht;
| ^~~~~~~~~~~~~
street_lamps.cpp:24:1: error: 'ht' does not name a type
24 | ht ft[300005];
| ^~
street_lamps.cpp: In function 'void update(int, int, int)':
street_lamps.cpp:30:10: error: 'ft' was not declared in this scope; did you mean 'f'?
30 | if(ft[a].find(x)==ft[a].end())ft[a][x]=upd;
| ^~
| f
street_lamps.cpp: In function 'int query(int, int)':
street_lamps.cpp:40:12: error: 'ft' was not declared in this scope; did you mean 'f'?
40 | ans+=ft[a][x];
| ^~
| f
street_lamps.cpp: In function 'int32_t main()':
street_lamps.cpp:50:24: warning: unused variable 'd' [-Wunused-variable]
50 | int prev=0,ans,a,b,c,d;
| ^
