C++(clang++11) 解法, 执行用时: 659ms, 内存消耗: 7032K, 提交时间: 2021-04-01 20:31:01

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
#define N 200005
int n,m,cnt,root;
char f[N];
inline void read(int &p)
{
	p=0;
	int f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') p=p*10+(ch-'0'),ch=getchar();
	p*=f;
}

struct node{
	int siz,key,ch[2],val,lmax[2],rmax[2],mx[2],sum1,RRev;
	int cov;
	bool rev;
	inline void Rev(){
		rev^=1;
		swap(lmax[0],lmax[1]);
		swap(rmax[0],rmax[1]);
		swap(mx[0],mx[1]);
		if(cov!=-1)cov^=1;
		sum1=siz-sum1;
		val^=1;
	}
	inline void Cov(int d){
		val=d;
		cov=d;
		sum1=(d?siz:0);
		for(int i=0;i<=1;i++){
			lmax[i]=rmax[i]=mx[i]=((d==i)?siz:0);
		}
	}
	void pushr(){
		swap(ch[0],ch[1]);
		swap(lmax[0],rmax[0]);
		swap(lmax[1],rmax[1]);
		RRev^=1;
	}
}t[N];
int NewNode(int data){
	int k=++cnt;
	t[k].val=t[k].sum1=data;
	t[k].siz=1;
	t[k].key=rand();
	t[k].ch[0]=t[k].ch[1]=0;
	t[k].rev=0;
	t[k].cov=-1;
	t[k].RRev=0;
	for(int i=0;i<=1;i++){
		t[k].lmax[i]=t[k].rmax[i]=t[k].mx[i]=(data==i);
	}
	return k;
}
inline void update(int k){
	t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+1;
	t[k].sum1=t[t[k].ch[0]].sum1+t[t[k].ch[1]].sum1+t[k].val;
	for(int i=0;i<=1;i++){
		t[k].lmax[i]=t[t[k].ch[0]].lmax[i];
		t[k].rmax[i]=t[t[k].ch[1]].rmax[i];
		t[k].mx[i]=max(t[t[k].ch[0]].mx[i],t[t[k].ch[1]].mx[i]);
		if(t[k].val==i){
			if(t[t[k].ch[0]].sum1==(i?t[t[k].ch[0]].siz:0)){
				t[k].lmax[i]+=1+t[t[k].ch[1]].lmax[i];
			}
			if(t[t[k].ch[1]].sum1==(i?t[t[k].ch[1]].siz:0)){
				t[k].rmax[i]+=1+t[t[k].ch[0]].rmax[i];
			}
			t[k].mx[i]=max(t[k].mx[i],t[t[k].ch[0]].rmax[i]+1+t[t[k].ch[1]].lmax[i]);
		}
	}
}
inline void pushdown(int k){
	if(t[k].rev){
		t[t[k].ch[0]].Rev();
		t[t[k].ch[1]].Rev();
		t[k].rev=0;
	}
	if(t[k].cov!=-1){
		t[t[k].ch[0]].Cov(t[k].cov);
		t[t[k].ch[1]].Cov(t[k].cov);
		t[k].cov=-1;
	}
	if(t[k].RRev){
		t[t[k].ch[0]].pushr(),t[t[k].ch[1]].pushr();
		t[k].RRev=0;
	}
}
int Merge(int l,int r){
	if(!l||!r)return l+r;
	pushdown(l),pushdown(r);
	if(t[l].key<t[r].key){
		t[l].ch[1]=Merge(t[l].ch[1],r);
		update(l);
		return l;
	}
	else{
		t[r].ch[0]=Merge(l,t[r].ch[0]);
		update(r);
		return r;
	}
}
void Split(int k,int data,int &l,int &r){
	if(!k){
		l=r=0;
		return ;
	}
	pushdown(k);
	if(t[t[k].ch[0]].siz+1<=data){
		l=k;
		Split(t[k].ch[1],data-t[t[k].ch[0]].siz-1,t[k].ch[1],r);
	}
	else{
		r=k;
		Split(t[k].ch[0],data,l,t[k].ch[0]);
	}
	update(k);
}
inline void Change(int x,int y,int d){
	int l,p,r;
	Split(root,y,l,r);
	Split(l,x-1,l,p);
	t[p].Cov(d);
	root=Merge(Merge(l,p),r);
}
inline void Rever(int x,int y){
	int l,p,r;
	Split(root,y,l,r);
	Split(l,x-1,l,p);
	t[p].pushr();
	root=Merge(Merge(l,p),r);
}
inline void Reverse(int x,int y){
	int l,p,r;
	Split(root,y,l,r);
	Split(l,x-1,l,p);
	t[p].Rev();
	root=Merge(Merge(l,p),r);
}
inline int Count1(int x,int y){
	int l,p,r;
	Split(root,y,l,r);
	Split(l,x-1,l,p);
	int ans=t[p].sum1;
	root=Merge(Merge(l,p),r);
	return ans;
}
inline int Ask_MX(int x,int y){
	int l,p,r;
	Split(root,y,l,r);
	Split(l,x-1,l,p);
	int ans=max(t[p].mx[0],t[p].mx[1]);
	root=Merge(Merge(l,p),r);
	return ans;
}
void output(int x)
{
	if(!x)	return;
	pushdown(x);
	output(t[x].ch[0]);
	printf("%d ",t[x].val);
	output(t[x].ch[1]);
}
int main()
{
	srand(time(0));
	read(n);read(m);
	cin>>f+1;
	for(int i=1;i<=n;i++)
	{
		if(f[i]=='0') root=Merge(root,NewNode(0));
		else root=Merge(root,NewNode(1));
	}
	
	for(int i=1;i<=m;i++)
	{
		int l,r,opt;
		read(opt);read(l);read(r);
		switch(opt)
		{
			case 1:
			{
				Reverse(l,r);
				break;
			}
			case 2:
			{
				Rever(l,r);
				break;
			}
			case 3:
			{
				int X=Count1(l,r);
				if(l<=l+(r-l+1-X)-1) Change(l,l+(r-l+1-X)-1,0);
				if(X>=1) Change(l+(r-l+1-X),r,1);
				break;
			}
			case 4:
			{
				Change(l,r,0);
				break;
			}
			case 5:
			{
				Change(l,r,1);
				break;
			}
		}
		printf("%d\n",Ask_MX(1,n));
	}
	return 0;
}