#include<bits/stdc++.h>
using namespace std;
//#define int long long
struct inter {
int debInter,finInter,typeInter,dateDeb;
bool operator < (const inter& autre) const {
if (debInter!=autre.debInter) {
return debInter < autre.debInter;
}
return finInter < autre.finInter;
}
};
struct passage {
int debInter,finInter,duree;
};
struct noeud {
int decalage=1;
set<int> toutNum;
unordered_map<int,int> corres;
vector<int> som;
};
const int MAX_VAL=300*1000+5,INFINI=1000*1000*1000,DECA=(1<<19);
int nbVal,nbReq;
int rep[MAX_VAL];
int quest[MAX_VAL][2];
int etatCour[MAX_VAL];
set<inter> enCours;
vector<passage> ajout[MAX_VAL];
noeud arb[2*DECA];
void maj(inter ancien,int nouvDate) {
enCours.erase(ancien);
if (nouvDate>ancien.dateDeb && ancien.typeInter==1) {
ajout[nouvDate].push_back({ancien.debInter,ancien.finInter,nouvDate-ancien.dateDeb});
//cout<<"!"<<nouvDate<<" : "<<ancien.debInter<<" "<<ancien.finInter<<" "<<nouvDate-ancien.dateDeb<<endl;
}
}
void modif(int pos,int nouvDate) {
auto it=enCours.lower_bound({pos,INFINI,0,0});
it--;
inter ancien=(*it);
maj(ancien,nouvDate);
int nouvDeb=pos,nouvFin=pos;
if (ancien.debInter<pos) {
enCours.insert({ancien.debInter,pos-1,ancien.typeInter,nouvDate});
}
else if (pos>1) {
it=enCours.lower_bound({pos,INFINI,0,0});
it--;
auto preced=(*it);
nouvDeb=preced.debInter;
maj(preced,nouvDate);
}
if (ancien.finInter>pos) {
enCours.insert({pos+1,ancien.finInter,ancien.typeInter,nouvDate});
}
else if (pos<nbVal) {
it=enCours.lower_bound({pos,INFINI,0,0});
auto suiv=(*it);
nouvFin=suiv.finInter;
maj(suiv,nouvDate);
}
enCours.insert({nouvDeb,nouvFin,1-ancien.typeInter,nouvDate});
}
void afficher() {
return;
for (inter i:enCours) {
cout<<i.debInter<<" "<<i.finInter<<" "<<i.typeInter<<" "<<i.dateDeb<<endl;
}
cout<<endl;
}
void marqueAjout(passage nouv) {
int pos=DECA+nouv.debInter;
while (pos>0) {
arb[pos].toutNum.insert(nouv.finInter);
pos/=2;
}
}
void marqueQuest(int deb,int fin,int finReq) {
if (deb==fin) {
arb[deb].toutNum.insert(finReq);
return;
}
if (deb%2==1) {
arb[deb].toutNum.insert(finReq);
marqueQuest(deb+1,fin,finReq);
return;
}
if (fin%2==0) {
arb[fin].toutNum.insert(finReq);
marqueQuest(deb,fin-1,finReq);
return;
}
marqueQuest(deb/2,fin/2,finReq);
}
void ajoutInter(passage nouv) {
int pos=DECA+nouv.debInter;
while (pos>0) {
int temp=arb[pos].corres[nouv.finInter]+arb[pos].decalage;
while (temp>0) {
arb[pos].som[temp]+=nouv.duree;
temp/=2;
}
pos/=2;
}
}
int calcSom(int deb,int fin,int idSom) {
if (deb==fin) {
return arb[idSom].som[deb];
}
if (deb%2==1) {
return arb[idSom].som[deb]+calcSom(deb+1,fin,idSom);
}
if (fin%2==0) {
return arb[idSom].som[fin]+calcSom(deb,fin-1,idSom);
}
return calcSom(deb/2,fin/2,idSom);
}
int calcQuest(int deb,int fin,int finReq) {
if (deb==fin) {
return calcSom(arb[deb].decalage+arb[deb].corres[finReq],2*arb[deb].decalage-1,deb);
}
if (deb%2==1) {
return calcSom(arb[deb].decalage+arb[deb].corres[finReq],2*arb[deb].decalage-1,deb)+calcQuest(deb+1,fin,finReq);
}
if (fin%2==0) {
return calcSom(arb[fin].decalage+arb[fin].corres[finReq],2*arb[fin].decalage-1,fin)+calcQuest(deb,fin-1,finReq);
}
return calcQuest(deb/2,fin/2,finReq);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>nbVal>>nbReq;
enCours.insert({1,nbVal,0,0});
for (int i=1;i<=nbVal;i++) {
char nouv;
cin>>nouv;
if (nouv=='1') {
modif(i,0);
}
}
afficher();
for (int i=1;i<=nbReq;i++) {
string typeOp;
cin>>typeOp;
if (typeOp=="query") {
int debReq,finReq;
cin>>debReq>>finReq;
finReq--;
quest[i][0]=debReq;
quest[i][1]=finReq;
auto it=enCours.lower_bound({debReq,INFINI,0,0});
it--;
if ((*it).finInter>=finReq && (*it).typeInter==1) {
rep[i]+=i-(*it).dateDeb;
//cout<<i<<" : "<<rep[i]<<endl;
}
}
else {
int posModif;
cin>>posModif;
modif(posModif,i);
afficher();
}
}
for (int i=1;i<=nbReq;i++) {
if (quest[i][0]==0) {
for (passage j:ajout[i]) {
marqueAjout(j);
}
}
else {
marqueQuest(DECA,DECA+quest[i][0],quest[i][1]);
}
}
for (int i=0;i<2*DECA;i++) {
int num=0;
for (int j:arb[i].toutNum) {
arb[i].corres[j]=num;
num++;
}
while (arb[i].decalage<num) {
arb[i].decalage*=2;
}
arb[i].som.resize(2*arb[i].decalage,0);
arb[i].toutNum.clear();
//cout<<i<<" : "<<num<<" "<<arb[i].decalage<<endl;
}
for (int i=1;i<=nbReq;i++) {
if (quest[i][0]==0) {
for (passage j:ajout[i]) {
//cout<<i<<" : "<<j.debInter<<" "<<j.finInter<<" "<<j.duree<<endl;
ajoutInter(j);
}
}
else {
rep[i]+=calcQuest(DECA,DECA+quest[i][0],quest[i][1]);
}
}
for (int i=1;i<=nbReq;i++) {
if (quest[i][0]!=0) {
cout<<rep[i]<<"\n";
}
}
}
