Description
为了简单起见，我们将大脑视作一个01序列。1代表这个位置的脑组织正常工作，0代表这是一块脑洞。
1 0 1 0 0 0 1 1 1 0
脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）
例如，用上面第8号位置到第10号位置去修补第1号位置到第4号位置的脑洞。我们就会得到：
1 1 1 1 0 0 1 0 0 0
如果再用第1号位置到第4号位置去修补第8号位置到第10号位置：
0 0 0 0 0 0 1 1 1 1
这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。
如果再用第7号位置到第10号位置去填补第1号位置到第6号位置：
1 1 1 1 0 0 0 0 0 0
这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。
假定初始时SHTSC并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答SHTSC的问题：在大脑某个区间中最大的连续脑洞区域有多大?
第一行两个整数n，m。表示SHTSC的大脑可分为从1到n编号的n个连续区域。有m个操作。
以下m行每行是下列三种格式之一。
0 l r ：SHTSC挖了一个从l到r的脑洞。
1 l0 r0 l1 r2 ：SHTSC进行了一次脑洞治疗，用从l0到r0的脑组织修补l1到r1的脑洞。
2 l r ：SHTSC询问l到r这段区间最大的脑洞有多大。
n,m <=200000，1<=l<=r<=n
线段树。区间染色+查询1的个数+维护区间连续0的最长长度，显然每次只会覆盖log个单独区间，将其的0改成1（最后一个整区间打散，其余的都直接染色）。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
char ch=nc(); x=0;
while(ch<'0'||ch>'9') ch=nc();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc();
}
int la[N<<2],ra[N<<2],ma[N<<2],si[N<<2],lz[N<<2],su[N<<2],sum;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline void pushup(int pos)
{
la[pos]=si[pos<<1] ? la[pos<<1] : la[pos<<1]+la[pos<<1|1];
ra[pos]=si[pos<<1|1] ? ra[pos<<1|1] : ra[pos<<1|1]+ra[pos<<1];
ma[pos]=Max(ma[pos<<1],Max(ma[pos<<1|1],ra[pos<<1]+la[pos<<1|1]));
si[pos]=si[pos<<1]+si[pos<<1|1];
}
inline void pd(int pos,int x)
{
la[pos]=x ? 0 : su[pos];
ma[pos]=ra[pos]=su[pos]-x;
si[pos]=x; lz[pos]=x;
}
inline void pushdown(int pos)
{
if(lz[pos]!=-1)
{
int tmp=Min(su[pos<<1],lz[pos]);
pd(pos<<1,tmp);
pd(pos<<1|1,lz[pos]-tmp);
lz[pos]=-1;
}
}
void build(int pos,int l,int r)
{
lz[pos]=-1; su[pos]=r-l+1;
if(l==r)
{
la[pos]=ra[pos]=ma[pos]=0;
si[pos]=1;
return ;
}
int mid=(l+r)>>1;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
pushup(pos);
}
int fix1(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
int tmp=Min(sum,su[pos]),re=si[pos];
pd(pos,tmp); sum-=tmp; return re;
}
int mid=(l+r)>>1,re; pushdown(pos);
if(y<=mid) re=fix1(pos<<1,l,mid,x,y);
else if(x>mid) re=fix1(pos<<1|1,mid+1,r,x,y);
else re=fix1(pos<<1,l,mid,x,y)+fix1(pos<<1|1,mid+1,r,x,y);
pushup(pos); return re;
}
void fix2(int pos,int l,int r,int x,int y)
{
if(!sum) return ;
if(x<=l&&y>=r)
{
if(sum>=su[pos]-si[pos])
{
sum-=su[pos]-si[pos];
pd(pos,su[pos]);
return ;
}
pushdown(pos);
if(sum>=su[pos<<1]-si[pos<<1])
{
sum-=su[pos<<1]-si[pos<<1];
pd(pos<<1,su[pos<<1]);
fix2(pos<<1|1,((l+r)>>1)+1,r,x,y);
}
else fix2(pos<<1,l,(l+r)>>1,x,y);
pushup(pos); return ;
}
int mid=(l+r)>>1; pushdown(pos);
if(y<=mid) fix2(pos<<1,l,mid,x,y);
else if(x>mid) fix2(pos<<1|1,mid+1,r,x,y);
else fix2(pos<<1,l,mid,x,y),fix2(pos<<1|1,mid+1,r,x,y);
pushup(pos);
}
int query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r) return ma[pos];
int mid=(l+r)>>1; pushdown(pos);
if(y<=mid) return query(pos<<1,l,mid,x,y);
else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
else return Max( Max( query(pos<<1,l,mid,x,y) ,
query(pos<<1|1,mid+1,r,x,y) ) ,
Min(mid-x+1,ra[pos<<1])+Min(y-mid,la[pos<<1|1]));
}
int main()
{
int n,m; read(n); read(m); build(1,1,n);
int sw,l0,r0,l1,r1;
while(m--)
{
read(sw); read(l0); read(r0);
if(sw==0) sum=0,fix1(1,1,n,l0,r0);
else if(sw==1)
{
read(l1); read(r1); sum=0;
sum=fix1(1,1,n,l0,r0);
fix2(1,1,n,l1,r1);
}
else printf("%d\n",query(1,1,n,l0,r0));
}
return 0;
}