传送门

---

话说中国赛区有人AKAPIO么？感觉这题非常适合中国OI选手做啊。。。

CDQ分治难道已经走到国际了么？ 不用CDQ就应该是用树套树，不是说外国选手数据结构水平人均线段树么（

哦，他们pbds比较强来着

题解：

首先把询问$(x,y)$看作是一个点，然后把询问转成矩形加，然后set维护一下连续段，然后CDQ分治+树状数组解决三维偏序即可。。。

所以这道题有难度么。。。

中国选手没AK的唯一原因应该是没有调出来吧，不太可能是不会做。。。

---

代码：

#include<bits/stdc++.h> #define ll long long #define re register #define cs const namespace IO{ static cs int Rlen=1<<22|1; static char buf[Rlen],*p1,*p2; inline char gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;} inline char pk(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1;} inline char ga(){while(!isalpha(pk()))++p1;return *p1++;} template<typename T>inline T get(){ char c;T num; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; }inline int gi(){return get<int>();} } using namespace IO; using std::cerr; using std::cout; cs int N=3e5+7; std::set<int> s; int n,q,tot;char str[N]; int R[N],las[N],vis[N],tr[N],ans[N]; struct node{int t,v,x,y;}t[N<<1|1],tp[N<<1|1]; inline void add(int p,int v){for(;p<=n;p+=p&-p)tr[p]+=v;} inline int qy(int p){int r=0;for(;p;p&=p-1)r+=tr[p];return r;} inline void clr(int p){for(;p<=n;p+=p&-p)tr[p]=0;} inline void solve(int l,int r){ if(l==r)return ;int mid=l+r>>1; solve(l,mid),solve(mid+1,r); int i=l,j=mid+1,p=l; while(i<=mid&&j<=r){ if(t[i].y>=t[j].y){tp[p++]=t[i];if(~t[i].v)add(t[i].x,t[i].v);++i;} else {tp[p++]=t[j];if(!~t[j].v)ans[t[j].t]+=qy(t[j].x);++j;} } while(i<=mid){tp[p++]=t[i];if(~t[i].v)add(t[i].x,t[i].v);++i;} while(j<=r){tp[p++]=t[j];if(!~t[j].v)ans[t[j].t]+=qy(t[j].x);++j;} for(int re i=l;i<=mid;++i)if(~t[i].v)clr(t[i].x); for(int re i=l;i<=r;++i)t[i]=tp[i]; } signed main(){ #ifdef zxyoi freopen("light.in","r",stdin); #endif scanf("%d%d%s",&n,&q,str+1); for(int re i=1;i<=n;++i)vis[i]=str[i]^48; for(int re i=1,j;i<=n;i=j+1){ while(i<=n&&!vis[i])++i; if(i>n)break;else j=i; while(j<=n&&vis[j])++j; s.insert(i),R[i]=j-1; }s.insert(0);R[0]=-1; memset(ans,-1,sizeof ans); for(int re j=1;j<=q;++j){ switch(ga()){ case 't':{ int x=gi(); if(!vis[x]){ int l=x,r=x; auto i=s.upper_bound(x); if(i!=s.end()&&*i==x+1){ t[++tot]=(node){j,j-las[*i],*i,R[*i]}; r=R[x+1];auto tp=i--;s.erase(tp); }else i--; if(R[*i]==x-1){ t[++tot]=(node){j,j-las[*i],*i,R[*i]}; l=*i;s.erase(i); }s.insert(l);R[l]=r;las[l]=j; }else { auto i=--s.upper_bound(x); t[++tot]=(node){j,j-las[*i],*i,R[*i]}; if(vis[x+1])s.insert(x+1),R[x+1]=R[*i],las[x+1]=j; if(x==*i)s.erase(i);else R[*i]=x-1,las[*i]=j; }vis[x]^=1; break; } case 'q':{ int l=gi(),r=gi()-1; t[++tot]=(node){j,-1,l,r}; auto i=--s.upper_bound(l); if(R[*i]>=r)ans[j]=j-las[*i]; else ans[j]=0; break; } } } solve(1,tot); for(int re i=1;i<=q;++i)if(~ans[i])cout<<ans[i]<<"\n"; return 0; }