洛谷题目页面传送门
题意见洛谷。
首先考虑实时维护(forall i,jin[1,n])，目前有多少时刻满足能从(i)到达(j)。
显然，(i)能到达(j)当且仅当(i,j)在同一个亮灯连续段里。将当前状态剖成若干个极大亮灯连续段，那么能否到达关于(i,j)两维的函数应该是由这些连续段，每段分别在(i)轴和(j)轴上作为两条邻边、(j=i)上的一段作为副对角线的一些充满(1)的正方形组成的，其他地方都是(0)。（别问为啥不贴图，问就是我不是良心博主）
那么在某一时刻的答案函数就是之前所有时刻的所对应的上述01函数之和。考虑实时维护这个答案函数（二维函数，即一个矩阵）。
一种很容易想到的方法是递推，每次将当前时刻的01函数加到当前维护的答案函数里面去。当前时刻的01函数显然是由上一时刻的01函数进行常数次矩形修改得来的（开灯就是连接两边接壤的(1)矩形并补全，关灯就是从所在(1)矩形断开，至于如何维护这些连续段，set即可，太简单不多说），而将01函数加到答案函数里去又等价于对答案矩阵进行若干次（这里不是常数次了，而是连续段个数次，即(1)矩形个数次）矩形增加(1)。这里对01函数的更新显然是力所能及的，而对答案函数的更新的复杂度就没法保证了。
不难发现，这里对01函数的更新是若干次矩形加(1)，其中(1)是个常数，而这些矩形随时刻递增又是常数差异的，就一脸可以优化成在这些常数级别的差异上增加非常数，从而保证复杂度。
考虑一个01函数关于时刻的三维函数。考虑当前答案函数的每一处在这个三维函数上的意义：显然是从当前时刻断开时间轴得到的纵切面的左边的所有此处的和。这是一些(0/1)的和，(0)显然不用考虑，剩下来就是一些(1)的区间，设为([l_1,r_1],[l_2,r_2],cdots,[l_k,r_k])，那么这个和就是(sumlimits_{i=1}^k(r_i-l_i+1))。考虑在一个区间开始的时候给此处贡献上(-l_i)，在区间结束的时候给此处贡献上(r_i+1)。此时增加量显然不是常数了，我们来看看增加次数有没有减少。区间开始和区间结束的时候，就是相邻01函数差异对此处影响的时候，每次时刻的递推都只有01函数差异的矩形量次矩形增加，哦吼，可以了。需要注意的是，若当前要查询的那处在01函数中为(1)的话，那么第(k)个区间还未结束，我们要强行令它结束，即在答案函数在此处的值的基础上再加上当前时刻。
（上面这一段重要的转化是本题的瓶颈。个人感觉这个哲学思想理解的还不是很透彻，大概以后重点做DS的时候题做多了感觉就上来了吧。）
接下来就是个矩形增加、单点查询的事了。看起来能够线段树套动态开点线段树，但写到一半才发现外层线段树的懒标记无法(mathrm O(1))存储。于是想到将修改和查询范围颠倒的方式：差分。考虑二维差分，这样一次矩形增加转化为(4)次单点增加，单点查询转化为前缀矩形求和。这就是个经典的二维数点模型，写一发BIT套动态开点线段树即可（萌新第一次写这个，多多关照）。二维数点应该是有其他方法的（如cdq分治），然而我还没有系统的学这一块，不管，而且这题重点不在这里。
btw，这是我第二次写vector动态开点数据结构（第一次是列队），犯了跟列队同样的错误（UB+vector分配内存原理造成赋不进去值）。多错几次就不会犯了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
const int inf=0x3f3f3f3f;
int lowbit(int x){return x&-x;}
const int N=300000;
int n,qu;
char a[N+5];
struct segtree{//动态开点线段树
struct node{int lson,rson,l,r,sum;};
#define lson(p) nd[p].lson
#define rson(p) nd[p].rson
#define l(p) nd[p].l
#define r(p) nd[p].r
#define sum(p) nd[p].sum
vector<node> nd;
int nwnd(int l=1,int r=n){return nd.pb(node({0,0,l,r,0})),nd.size()-1;}
void init(){//初始化
nd.pb(node({0,0,0,0,0}));
nwnd();
}
void add(int x,int v,int p=1){//单点增加
sum(p)+=v;
if(l(p)==r(p))return;
int mid=l(p)+r(p)>>1,res;
if(x<=mid){
if(!lson(p))res=nwnd(l(p),mid),lson(p)=res;
add(x,v,lson(p));
}
else{
if(!rson(p))res=nwnd(mid+1,r(p)),rson(p)=res;
add(x,v,rson(p));
}
}
int _sum(int l,int r,int p=1){//区间求和
if(!p)return 0;
if(l<=l(p)&&r>=r(p))return sum(p);
int mid=l(p)+r(p)>>1,res=0;
if(l<=mid)res+=_sum(l,r,lson(p));
if(r>mid)res+=_sum(l,r,rson(p));
return res;
}
};
struct bitree{//BIT
segtree segt[N+1];
void init(){//初始化
for(int i=1;i<=n;i++)segt[i].init();
}
void add(int x,int y,int v){
if(y>n)return;
while(x<=n)segt[x].add(y,v),x+=lowbit(x);
}
void add(int l1,int r1,int l2,int r2,int v){//矩形增加
add(r1+1,r2+1,v);add(l1,r2+1,-v);add(r1+1,l2,-v);add(l1,l2,v);//转化为差分数组上的单点增加
}
int val(int x,int y){//单点查询
int res=0;
while(x)res+=segt[x]._sum(1,y),x-=lowbit(x);//转化为差分数组上的矩形求和
return res;
}
}bit;
int main(){
cin>>n>>qu;
scanf("%s",a+1);
set<pair<int,int> > st;
for(int i=1,las=0;i<=n+1;i++)
if(a[i]=='1')las=las?las:i;
else if(las)st.insert(mp(las,i-1)),las=0;
bit.init();
for(int i=1;i<=qu;i++){
char tp[10];int x,y;
scanf(" %s%d",tp,&x);
if(tp[0]=='t'){
set<pair<int,int> >::iterator fd=st.upper_bound(mp(x,inf));
if(fd!=st.begin()&&x<=(--fd)->Y){//关灯
int l=fd->X,r=fd->Y;
st.erase(fd);
bit.add(l,r,l,r,i);
if(l<x)st.insert(mp(l,x-1)),bit.add(l,x-1,l,x-1,-i);
if(r>x)st.insert(mp(x+1,r)),bit.add(x+1,r,x+1,r,-i);
}
else{//开灯
fd=st.upper_bound(mp(x,inf));
int l=x,r=x;
if(fd!=st.begin())fd--,fd->Y==x-1?bit.add(fd->X,fd->Y,fd->X,fd->Y,i),l=fd->X,st.erase(fd++):fd++;
if(fd!=st.end())fd->X==x+1&&(bit.add(fd->X,fd->Y,fd->X,fd->Y,i),r=fd->Y,st.erase(fd),0);
st.insert(mp(l,r));
bit.add(l,r,l,r,-i);
}
}
else{
scanf("%d",&y);y--;
set<pair<int,int> >::iterator fd=st.upper_bound(mp(x,inf));
if(fd!=st.begin()&&y<=(--fd)->Y)printf("%d
",bit.val(x,y)+i);
else printf("%d
",bit.val(x,y));
}
}
return 0;
}