/**********************************************
题目大意：
0 a b将区间[a,b]所有数全部变成0
1 a b将区间[a,b]所有数全部变成1
2 a b将区间[a,b]中所有数0 1互换，0变1,1变0
3 a b输出区间[a,b]中1的个数
4 a b输出区间[a,b]中最长连续1的个数
算法分析：
涉及到线段树的多种操作;
0,1两种操作可以合并到一起写;
0,1互换即线段树的异或操作;
查询区间最长连续1个数的过程中;
maxl=[l,m]上最长连续1个数;
maxl=[m+1,r]上最长连续1的个数;
maxm=min(m-l+1,左孩子的rs)+min(r-m,右孩子的ls);
结果应该是这三个中的最大值,即max(maxl,maxr,maxm);
其中查询操作和pku3667类似;
***********************************************/
#include
#include
#include
#include
#include
#include
using namespace std;
#define L l,m,u<<1
#define R m+1,r,u<<1|1
const int N =100010;
struct node
{
int l,r;
int ls,ms,rs;//ls左边最长连续1数量;ms:最长连续1数量;rs:右边最长连续1数量;
int flag;//01状态
int total;//区间1的总数
} t[N*3];
int len(int u)
{
return t[u].r-t[u].l+1;
}
int mid(int u)
{
return (t[u].l+t[u].r)>>1;
}
void PushUp(int u,int x)//把当前结点的信息更新到父结点
{
t[u].ls=t[u].ms=t[u].rs=t[u].total=x*(t[u].r-t[u].l+1);
t[u].flag=x;
}
void build(int l,int r,int u)//建树
{
t[u].l=l;
t[u].r=r;
t[u].ls=t[u].rs=t[u].ms=t[u].total=t[u].flag=0;
if(l==r)
return;
int m=mid(u);
build(L);
build(R);
}
void PushUp(int u)//把当前结点的信息更新到父结点
{
t[u].flag=(t[u<<1].flag==t[u<<1|1].flag t[u<<1].flag:-1);//更新状态
t[u].ls=t[u<<1].ls+((t[u<<1].ls==len(u<<1)) t[u<<1|1].ls:0);//更新左
t[u].rs=t[u<<1|1].rs+((t[u<<1|1].rs==len(u<<1|1)) t[u<<1].rs:0);//更新右
t[u].ms=max(t[u<<1].rs+t[u<<1|1].ls,max(t[u<<1].ms,t[u<<1|1].ms));//更新整体
t[u].total=t[u<<1].total+t[u<<1|1].total;//更新1的总数
}
void update(int l,int r,int u,int x)//更新区间[l,r]0、1状态
{
if(t[u].flag==x)
return;
if(t[u].l==l&&t[u].r==r)
{
PushUp(u,x);
return;
}
if(t[u].flag>
=0)
{
PushUp(u<<1,t[u].flag);
PushUp(u<<1|1,t[u].flag);
t[u].flag=-1;
}
int m=mid(u);
if(r<=m)
{
update(l,r,u<<1,x);
}
else if(l>m)
{
update(l,r,u<<1|1,x);
}
else
{
update(L,x);
update(R,x);
}
PushUp(u);
}
void swap(int l,int r,int u)//[l,r]0、1交换
{
if(t[u].l>=l&&t[u].r<=r&&(t[u].flag==0||t[u].flag==1))
{
int x=t[u].flag^1;
PushUp(u,x);
return;
}
if(t[u].flag>=0)
{
PushUp(u<<1,t[u].flag);
PushUp(u<<1|1,t[u].flag);
}
int m=mid(u);
if(r<=m)
{
swap(l,r,u<<1);
}
else if(l>m)
{
swap(l,r,u<<1|1);
}
else
{
swap(L);
swap(R);
}
PushUp(u);
}
int find1(int l,int r,int u)//找区间[l,r]内的1的个数
{
if(t[u].l==l&&t[u].r==r)
{
return t[u].total;
}
if(t[u].flag>=0)
{
PushUp(u<<1,t[u].flag);
PushUp(u<<1|1,t[u].flag);
}
int m=mid(u);
if(r<=m)
{
return find1(l,r,u<<1);
}
else if(l>m)
{
return find1(l,r,u<<1|1);
}
else
{
return find1(L)+find1(R);
}
}
int find2(int l,int r,int u)//找区间[l,r]内最长连续1的个数
{
if(t[u].l==l&&t[u].r==r)
{
return t[u].ms;
}
if(t[u].flag>=0)
{
PushUp(u<<1,t[u].flag);
PushUp(u<<1|1,t[u].flag);
}
int m=mid(u);
if(r<=m)
{
return find2(l,r,u<<1);
}
else if(l>m)
{
return find2(l,r,u<<1|1);
}
else
{
int maxl=find2(L);//[l,m]上最长连续1个数
int maxr=find2(R);//[m+1,r]上最长连