C++ 解法, 执行用时: 1841ms, 内存消耗: 76716K, 提交时间: 2022-03-18 22:12:37

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE)&&defined(LOCAL)
#include "my_header\debug.h"
#else
#define dbg(...) ;
#define dbgn(...) ;
#endif
inline char gc() {
    static char buf[1048576], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1048576, stdin),
    p1 == p2) ? EOF : *p1++;
}
inline int read() {
    char ch = gc(); int r = 0, w = 1;
    for (; ch < '0' || ch > '9'; ch = gc()) if (ch == '-') w = -1;
    for (; '0' <= ch && ch <= '9'; ch = gc()) r = r * 10 + (ch - '0');
    return r * w;
}
typedef unsigned int ui;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int N=1e6+5,M=4e6,inf=1e6+2;
char S[N],T[N*2];
struct Q
{
	int a00,a01,a10,a11;
	Q operator*(const Q &o) const
	{
		return {
			min(a00+o.a00,a01+o.a10),
			min(a00+o.a01,a01+o.a11),
			min(a10+o.a00,a11+o.a10),
			min(a10+o.a01,a11+o.a11)
		};
	}
};
Q ans,s[M];
const Q b[2]={{1,0,1,inf},{1,0,inf,0}};
Q bs[2][N];
int lz[M];
void build(int x,int l,int r)
{
	lz[x]=-1;
	if (l==r)
	{
		s[x]=b[S[l]];
		return;
	}
	int c=x*2,m=l+r>>1;
	build(c,l,m);build(c+1,m+1,r);
	s[x]=s[c]*s[c+1];
}
int z,y,dt;
void mdf(int x,int l,int r)
{
	if (z<=l&&r<=y) {lz[x]=dt;s[x]=bs[dt][r-l+1];return;}
	int c=x*2,m=l+r>>1;
	if (~lz[x])
	{
		lz[c]=lz[c+1]=lz[x];
		s[c]=bs[lz[x]][m-l+1];
		s[c+1]=bs[lz[x]][r-m];
		lz[x]=-1;
	}
	if (z<=m) mdf(c,l,m);
	if (y>m) mdf(c+1,m+1,r);
	s[x]=s[c]*s[c+1];
}
int fir;
void ask(int x,int l,int r)
{
	if (z<=l&&r<=y)
	{
		if (!fir) ans=ans*s[x]; else ans=s[x],fir=0;
		return;
	}
	int c=x*2,m=l+r>>1;
	if (~lz[x])
	{
		lz[c]=lz[c+1]=lz[x];
		s[c]=bs[lz[x]][m-l+1];
		s[c+1]=bs[lz[x]][r-m];
		lz[x]=-1;
	}
	if (z<=m) ask(c,l,m);
	if (y>m) ask(c+1,m+1,r);
}
int main()
{
	int n,m,i,j;
	n=read();m=read();
    for (i=1;i<=n;i++)
    {
        S[i]=gc();
        while (S[i]<'0'||S[i]>'1') S[i]=gc();
        S[i]-='0';
    }
	build(1,1,n);
	for (i=0;i<=1;i++)
	{
		bs[i][1]=b[i];
		for (j=2;j<=n;j++) bs[i][j]=bs[i][j-1]*b[i];
	}
	int ii=0;
	while (m--)
	{
		int op,l,r;
        op=read();l=read();r=read();
		if (!op)
		{
			z=l;y=r;dt=read();
			mdf(1,1,n);
		}
		else
		{
			fir=1;
			z=l;y=n;
			ask(1,1,n);
			z=1;y=l-1;
			if (y) ask(1,1,n);
			++ii;
			T[ii]='0'+(ans.a11<=r);
		}
	}
	cout<<T+1<<endl;
}