题目
题目描述
lxhgww最近收到了一个01序列，序列里面包含了n个数，这些数要么是0，要么是1，现在对于这个序列有五种变换操作和询问操作：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
对于每一种询问操作，lxhgww都需要给出回答，聪明的程序员们，你们能帮助他吗？
输入输出格式
输入格式：
输入数据第一行包括2个数，n和m，分别表示序列的长度和操作数目
第二行包括n个数，表示序列的初始状态
接下来m行，每行3个数，op, a, b，（0<=op<=4，0<=a<=b<n）表示对于区间[a, b]执行标号为op的操作
输出格式：
对于每一个询问操作，输出一行，包括1个数，表示其对应的答案
输入输出样例
输入样例#1：
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
输出样例#1：
5
2
6
5
说明
对于30%的数据，1<=n, m<=1000
对于100%的数据，1<=n, m<=100000
题解
这个题的细节很麻烦……定义线段树：
$sum$:这段区间内$1$的总数
$Lb$:这段区间内连续$0$的最大长度
$Lw$:这段区间内连续$1$的最大长度
$llb$:这段区间从左端点连续$0$的最大长度
$llw$:这段区间从左端点连续$1$的最大长度
$rlb$:这段区间从右端点连续$0$的最大长度
$rlw$:这段区间从右端点连续$1$的最大长度
$fl$:翻转标记
$lazy$:下推标记（记录是否全赋为$1$或$0$）
好乱…
可以找出上推关系式：（$0$表示左儿子，$1$表示右儿子）
$sum=sum_0+sum_1$
$Lb=max(Lb_0,Lb_1,rlb_0+llb_1)$（$Lw$同理）
$if(llb_0==mid-l+1)$ $llb=llb_0+llb_1$（$llw$同理）
$if(rlb_1==r-mid)$ $rlb=rlb_1+rlb_0$（$rlw$同理)
然而最恶心的是标记下推，$lazy$的优先级肯定大于翻转标记（全变为一个数就把翻转结果覆盖了）
所以先判断$lazy$,如果有$lazy$,左右儿子的翻转标记都要清空
然后就是慢慢打代码了…
代码
# include<iostream>
# include<cstdio>
# include<cstring>
# define mid (l+r>>1)
# define tl (k<<1)
# define tr (k<<1|1)
using namespace std;
const int MAX=1e5+1;
struct p{
int sum,Lw,Lb,llw,rlw,llb,rlb,lazy,fl;
}s[MAX<<2];
int n,m;
int max(int x,int y)
{
return x>y?x:y;
}
void pus(int l,int r,int k)
{
s[k].sum=s[tl].sum+s[tr].sum;
s[k].Lb=max(s[tl].Lb,s[tr].Lb);
s[k].Lw=max(s[tl].Lw,s[tr].Lw);
s[k].llb=s[tl].llb;
s[k].llw=s[tl].llw;
if(s[tl].llw==mid-l+1)
s[k].llw+=s[tr].llw;
if(s[tl].llb==mid-l+1)
s[k].llb+=s[tr].llb;
s[k].rlb=s[tr].rlb;
s[k].rlw=s[tr].rlw;
if(s[tr].rlw==r-mid)
s[k].rlw+=s[tl].rlw;
if(s[tr].rlb==r-mid)
s[k].rlb+=s[tl].rlb;
s[k].Lw=max(s[k].Lw,s[tl].rlw+s[tr].llw);
s[k].Lb=max(s[k].Lb,s[tl].rlb+s[tr].llb);
}
void down(int l,int r,int k)
{
int f=s[k].lazy,fl=s[k].fl,L1=mid-l+1,L2=r-mid;
s[k].lazy=-1;
if(!f)
{
s[tl]=(p){0,0,L1,0,0,L1,L1,0,0};
s[tr]=(p){0,0,L2,0,0,L2,L2,0,0};
}
else if(f==1)
{
s[tl]=(p){L1,L1,0,L1,L1,0,0,1,0};
s[tr]=(p){L2,L2,0,L2,L2,0,0,1,0};
}
if(fl)
{
s[k].fl=0;
int sum=s[tl].sum,Lw=s[tl].Lw,Lb=s[tl].Lb,llw=s[tl].llw,rlw=s[tl].rlw,llb=s[tl].llb,rlb=s[tl].rlb;
s[tl].sum=L1-sum;
s[tl].Lw=Lb,s[tl].Lb=Lw;
s[tl].llw=llb,s[tl].rlw=rlb;
s[tl].llb=llw,s[tl].rlb=rlw;
s[tl].fl^=1;
sum=s[tr].sum,Lw=s[tr].Lw,Lb=s[tr].Lb,llw=s[tr].llw,rlw=s[tr].rlw,llb=s[tr].llb,rlb=s[tr].rlb;
s[tr].sum=L2-sum;
s[tr].Lw=Lb,s[tr].Lb=Lw;
s[tr].llw=llb,s[tr].rlw=rlb;
s[tr].llb=llw,s[tr].rlb=rlw;
s[tr].fl^=1;
}
}
void build(int l,int r,int k)
{
s[k].lazy=-1;
if(l==r)
{
int x;
scanf("%d",&x);
s[k]=(p){x,x,(x^1),x,x,(x^1),(x^1),-1,0};
return;
}
build(l,mid,tl);
build(mid+1,r,tr);
pus(l,r,k);
}
void change1(int l,int r,int k,int L,int R)
{
if(l>=L&&r<=R)
{
int LL=r-l+1;
s[k]=(p){0,0,LL,0,0,LL,LL,0,0};
return;
}
if(l>R||r<L) return;
down(l,r,k);
change1(l,mid,tl,L,R);
change1(mid+1,r,tr,L,R);
pus(l,r,k);
}
void change2(int l,int r,int k,int L,int R)
{
if(l>=L&&r<=R)
{
int LL=r-l+1;
s[k]=(p){LL,LL,0,LL,LL,0,0,1,0};
return;
}
if(l>R||r<L) return;
down(l,r,k);
change2(l,mid,tl,L,R);
change2(mid+1,r,tr,L,R);
pus(l,r,k);
}
void change3(int l,int r,int k,int L,int R)
{
if(l>=L&&r<=R)
{
int LL=r-l+1,sum=s[k].sum,Lw=s[k].Lw,Lb=s[k].Lb,llw=s[k].llw,rlw=s[k].rlw,llb=s[k].llb,rlb=s[k].rlb;
s[k]=(p){LL-sum,Lb,Lw,llb,rlb,llw,rlw,s[k].lazy,(s[k].fl^1)};
return;
}
if(l>R||r<L) return;
down(l,r,k);
change3(l,mid,tl,L,R);
change3(mid+1,r,tr,L,R);
pus(l,r,k);
}
int ask1(int l,int r,int k,int L,int R)
{
if(l>=L&&r<=R) return s[k].sum;
if(l>R||r<L) return 0;
down(l,r,k);
return ask1(l,mid,tl,L,R)+ask1(mid+1,r,tr,L,R);
}
p ask2(int l,int r,int k,int L,int R)
{
if(l>=L&&r<=R) return s[k];
if(l>R||r<L) return (p){0};
down(l,r,k);
p LL=ask2(l,mid,tl,L,R),RR=ask2(mid+1,r,tr,L,R),ans;
ans.sum=LL.sum+RR.sum;
ans.Lw=max(LL.Lw,RR.Lw);
ans.Lb=max(LL.Lb,RR.Lb);
ans.llw=LL.llw,ans.rlw=RR.rlw;//
ans.llb=LL.llb,ans.rlb=RR.rlb;//
if(LL.llb==mid-l+1) ans.llb+=RR.llb;
if(LL.llw==mid-l+1) ans.llw+=RR.llw;
if(RR.rlb==r-mid) ans.rlb+=LL.rlb;
if(RR.rlw==r-mid) ans.rlw+=LL.rlw;
ans.Lw=max(ans.Lw,LL.rlw+RR.llw);
ans.Lb=max(ans.Lb,LL.rlb+RR.llb);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;i++)
{
int op,a,b;
scanf("%d%d%d",&op,&a,&b);
a++,b++;
if(!op) change1(1,n,1,a,b);
else if(op==1) change2(1,n,1,a,b);
else if(op==2) change3(1,n,1,a,b);
else if(op==3) printf("%d\n",ask1(1,n,1,a,b));
else if(op==4) printf("%d\n",ask2(1,n,1,a,b).Lw);
}
return 0;
}
