题面传送门 首先用两颗线段树维护每个点所在的亮灯联通块。 然后再建一颗二维线段树，每个点表示到当前为止，有多少个时刻能从 i i i到 j j j。 对于每次修改，依靠两颗线段树维护的区间，来修改。 这里有一个小技巧，在修改时加上 q − t q-t q−t，修改时减去，就是答案，还能累加。 查询就查当前点就好了。 代码实现:
#include<cstdio> using namespace std; int n,m,k,x,y,z,tot,root[300039],a[300039]; char s; struct tree{int l,r,f;}f[90000039]; struct set{ int f[1200039]; inline void jianshu(int l,int r,int now){ if(l==r){f[now]=l;return;} int m=(l+r)>>1; jianshu(l,m,now<<1);jianshu(m+1,r,now<<1|1); } inline void push(int now){ if(f[now]){ f[now<<1]=f[now<<1|1]=f[now]; f[now]=0; } } inline void get(int x,int y,int z,int l,int r,int now){ if(x<=l&&r<=y){f[now]=z;return;} int m=(l+r)>>1; push(now); if(x<=m) get(x,y,z,l,m,now<<1); if(y>m) get(x,y,z,m+1,r,now<<1|1); } inline int find(int x,int l,int r,int now){ if(l==r) return f[now]; push(now); int m=(l+r)>>1; if(x<=m) return find(x,l,m,now<<1); else return find(x,m+1,r,now<<1|1); } }fs[2]; inline void gets(int x,int y,int l,int r,int now){ f[now].f+=y; if(l==r) return; int m=(l+r)>>1; if(x<=m) { if(!f[now].l) f[now].l=++tot; gets(x,y,l,m,f[now].l); } else{ if(!f[now].r) f[now].r=++tot; gets(x,y,m+1,r,f[now].r); } } inline void get(int x,int y,int z){ if(y>n+1) return; while(x<=k){ if(!root[x]) root[x]=++tot; gets(y,z,1,k,root[x]); x+=x&-x; } } inline int finds(int x,int y,int l,int r,int now){ if(x<=l&&r<=y) return f[now].f; int m=(l+r)>>1,fs=0; if(x<=m&&f[now].l) fs+=finds(x,y,l,m,f[now].l); if(y>m&&f[now].r) fs+=finds(x,y,m+1,r,f[now].r); return fs; } inline int find(int x,int y){ int ans=0; while(x){ if(root[x]) ans+=finds(1,y,1,k,root[x]); x-=x&-x; } return ans; } int main(){ // freopen("12","r",stdin); // freopen("1.out","w",stdout); register int i; scanf("%d%d",&n,&m);k=n+1; for(i=1;i<=n;i++){ s=getchar(); while(s<'0'||s>'9') s=getchar(); a[i]=s-'0'; } fs[1].jianshu(1,k,1);fs[0].jianshu(1,k,1); for(i=1;i<=n;i++){ if(a[i]){ x=fs[0].find(i,1,k,1);y=fs[1].find(i+1,1,k,1); get(i+1,y+1,m);get(x,i+1,m);get(x,y+1,-m);get(i+1,i+1,-m); fs[0].get(x,y,x,1,k,1);fs[1].get(x,y,y,1,k,1); //printf("%d %d %d\n",x,y,tot); } } for(i=1;i<=m;i++){ s=getchar(); while(s<'a'||s>'z') s=getchar(); if(s=='q'){ s=getchar();s=getchar();s=getchar();s=getchar(); scanf("%d%d",&x,&y); z=fs[1].find(x,1,k,1); if(y>z) printf("%d\n",find(x,y)); else printf("%d\n",find(x,y)-(m-i)); } else{ s=getchar();s=getchar();s=getchar();s=getchar();s=getchar(); scanf("%d",&z); a[z]^=1; if(a[z]){ x=fs[0].find(z,1,k,1);y=fs[1].find(z+1,1,k,1); //printf("%d %d\n",x,y); get(z+1,y+1,m-i);get(x,z+1,m-i);get(x,y+1,-m+i);get(z+1,z+1,-m+i); fs[0].get(x,y,x,1,k,1);fs[1].get(x,y,y,1,k,1); } else{ //if(z==2)printf("%d %d\n",x,y); x=fs[0].find(z,1,k,1);y=fs[1].find(z,1,k,1); get(z+1,y+1,-m+i);get(x,z+1,-m+i);get(x,y+1,m-i);get(z+1,z+1,m-i); fs[1].get(x,z,z,1,k,1); fs[0].get(z+1,y,z+1,1,k,1); } } //printf("%d %d\n",fs[0].find(2,1,k,1),fs[1].find(2,1,k,1)); } }