题意：
分析：
- 暴力：
(O(nq)) 的暴力没有什么意义，我们换一个思路，我们对于询问的区间进行莫队，然后统计前缀中 (r-l+1) 的位置有多少个，这个可以用线段树维护，每一个节点维护一个 pair ，重载一下取 (max) ，复杂度也许是 (O(nsqrt nlog ))，实际得分 60pts
- 正解
我们考虑每一个一操作带来的影响，每一次会将两个连通块并为一个，或者反向裂开，我们每一次添加会增加新的连续段为 ((l,r)|(lle xle y)) 这些连续段在二维平面上其实是一个矩形，也就是说每一次我们会给一个矩形整体加上一段时间，这个矩形 (M_{i,j}) 表示区间 ([i,j]) 之间联通的时间，所以我们要实现矩形加单点查询，转化一下改成差分加，前缀和查询，直接树套树，复杂度 (O(nlog ^2))，对于找连通块的操作可以用线段树维护区间左端点，右端点，或者上 (set) 也可以
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register
using namespace std;
namespace zzc
{
typedef long long ll;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 1e6+5;
int n,qt,tot;
int rt[maxn],ch[maxn<<5][2],val[maxn<<5],pre[maxn<<1],suf[maxn<<1];
char st[maxn],opt[10];
int lowbit(int x) {return x&(-x);}
void pushup(int rt)
{
val[rt]=val[ch[rt][0]]+val[ch[rt][1]];
}
void pushdown(int rt)
{
if(pre[rt])
{
pre[lc]=pre[rt];
pre[rc]=pre[rt];
pre[rt]=0;
}
if(suf[rt])
{
suf[lc]=suf[rt];
suf[rc]=suf[rt];
suf[rt]=0;
}
}
void modify2(int &rt,int l,int r,int pos,int w)//¶¯Ì¬¿ªµãÏ߶ÎÊ÷
{
if(!rt) rt=++tot;
if(l==r)
{
val[rt]+=w;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) modify2(ch[rt][0],l,mid,pos,w);
else modify2(ch[rt][1],mid+1,r,pos,w);
pushup(rt);
}
int query2(int rt,int l,int r,int ql,int qr)//¶¯Ì¬¿ªµãÏ߶ÎÊ÷
{
if(ql<=l&&r<=qr) return val[rt];
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=query2(ch[rt][0],l,mid,ql,qr);
if(qr>mid) res+=query2(ch[rt][1],mid+1,r,ql,qr);
return res;
}
void modify1(int x,int y,int w)//Ê÷×´Êý×é
{
if(y>n+1) return ;
for(reg int i=x;i<=n+1;i+=lowbit(i)) modify2(rt[i],1,n+1,y,w);
}
int query1(int x,int y)//Ê÷×´Êý×é
{
int res=0;
for(reg int i=x;i;i-=lowbit(i)) res+=query2(rt[i],1,n+1,1,y);
return res;
}
void build(int rt,int l,int r)
{
if(l==r)
{
pre[rt]=l;
suf[rt]=l;
return ;
}
int mid=(l+r)>>1;
build(lc,l,mid);build(rc,mid+1,r);
}
void modify3(int rt,int l,int r,int ql,int qr,int w,int kind)//ÆÕͨÏ߶ÎÊ÷£ºÁ¬Í¨ÐÔ
{
if(ql<=l&&r<=qr)
{
if(kind==0) pre[rt]=w;
else suf[rt]=w;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(ql<=mid) modify3(lc,l,mid,ql,qr,w,kind);
if(qr>mid) modify3(rc,mid+1,r,ql,qr,w,kind);
}
int query3(int rt,int l,int r,int pos,int kind)//ÆÕͨÏ߶ÎÊ÷£ºÁ¬Í¨ÐÔ
{
if(l==r)
{
if(kind==0) return pre[rt];
else return suf[rt];
}
pushdown(rt);
int mid=(l+r)>>1;
if(pos<=mid) return query3(lc,l,mid,pos,kind);
else return query3(rc,mid+1,r,pos,kind);
}
bool connect(int x,int y)
{
return query3(1,1,n+1,x,0)==query3(1,1,n+1,y,0);
}
void insert(int x,int now)
{
int l=query3(1,1,n+1,x,0),r=query3(1,1,n+1,x+1,1);
modify3(1,1,n+1,l,x,r,1);
modify3(1,1,n+1,x+1,r,l,0);
modify1(l,x+1,qt-now);modify1(x+1,x+1,now-qt);
modify1(l,r+1,now-qt);modify1(x+1,r+1,qt-now);
}
void delet(int x,int now)
{
int l=query3(1,1,n+1,x,0),r=query3(1,1,n+1,x+1,1);
modify3(1,1,n+1,l,x,x,1);modify3(1,1,n+1,x+1,r,x+1,0);
modify1(l,x+1,now-qt);modify1(x+1,x+1,qt-now);
modify1(l,r+1,qt-now);modify1(x+1,r+1,now-qt);
}
void work()
{
int x,y,ans;
n=read();qt=read();
scanf("%s",st+1);build(1,1,n+1);
for(reg int i=1;i<=n;i++) if(st[i]=='1') insert(i,0);
for(reg int i=1;i<=qt;i++)
{
scanf("%s",opt);
if(opt[0]=='q')
{
x=read();y=read();
query3(1,1,n+1,4,0);
ans=query1(x,y);
if(connect(x,y)) ans-=qt-i;
printf("%d
",ans);
}
else
{
x=read();
if(connect(x,x+1)) delet(x,i);
else insert(x,i);
}
}
}
}
int main()
{
zzc::work();
return 0;
}