https://www.zybuluo.com/ysner/note/1297872
题面
(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)都需要给出回答，聪明的程序员们，你们能帮助他吗？
- (nleq10^5)
解析
真 线段树模板题。
只是要维护许多信息，考验细节和代码能力而已。
蒟蒻维护了(12)个：
(lt1[x])这一段左边有多少个连续的(1)；
(rt1[x])这一段右边有多少个连续的(1)；
(lt0[x])这一段左边有多少个连续的(0)；
(rt0[x])这一段右边有多少个连续的(0)；
(tag0[x])这一段是否全部为(0);
(tag1[x])这一段是否全部为(1);
(t1[x])这一段最多有多少个连续的(1);
(t0[x])这一段最多有多少个连续的(0);
(s[x])这一段有多少个(1)
(la0[x],la1[x],la2[x])前三个操作的懒标记。
难度集中在信息合并：
讲了没意思，有需要自己看代码吧。
我是不会承认我调了(3h)只因没有意识到两个操作(2)是可以抵消的。。。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=4e5+100;
int n,m,t1[N],t0[N],lt1[N],rt1[N],lt0[N],rt0[N],s[N],tag0[N],tag1[N],la0[N],la1[N],la2[N];
il int max(re int x,re int y){return x>y?x:y;}
il int min(re int x,re int y){return x<y?x:y;}
struct dat{int t1,lt1,rt1,tag1;};
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void upd(re int x)
{
s[x]=s[ls]+s[rs];
t1[x]=max(t1[ls],t1[rs]);
t1[x]=max(t1[x],rt1[ls]+lt1[rs]);
t0[x]=max(t0[ls],t0[rs]);
t0[x]=max(t0[x],rt0[ls]+lt0[rs]);
if(tag1[ls]) lt1[x]=lt1[ls]+lt1[rs];else lt1[x]=lt1[ls];
if(tag1[rs]) rt1[x]=rt1[rs]+rt1[ls];else rt1[x]=rt1[rs];
if(tag0[ls]) lt0[x]=lt0[ls]+lt0[rs];else lt0[x]=lt0[ls];
if(tag0[rs]) rt0[x]=rt0[rs]+rt0[ls];else rt0[x]=rt0[rs];
t1[x]=max(t1[x],max(lt1[x],rt1[x]));
t0[x]=max(t0[x],max(lt0[x],rt0[x]));
tag1[x]=tag1[ls]&tag1[rs];tag0[x]=tag0[ls]&tag0[rs];
}
il void Build(re int x,re int l,re int r)
{
if(l==r)
{
lt1[x]=rt1[x]=s[x]=t1[x]=tag1[x]=gi();
if(!t1[x]) t0[x]=lt0[x]=rt0[x]=tag0[x]=1;
return;
}
re int mid=l+r>>1;
Build(ls,l,mid);Build(rs,mid+1,r);
upd(x);
}
il void cover(re int x,re int l,re int r,re int op)
{
if(op==0)
{
s[x]=t1[x]=lt1[x]=rt1[x]=tag1[x]=0;
t0[x]=lt0[x]=rt0[x]=r-l+1;
tag0[x]=la0[x]=1;la1[x]=la2[x]=0;
}
if(op==1)
{
s[x]=t1[x]=lt1[x]=rt1[x]=r-l+1;
t0[x]=lt0[x]=rt0[x]=tag0[x]=0;
tag1[x]=la1[x]=1;la0[x]=la2[x]=0;
}
if(op==2)
{
swap(t1[x],t0[x]);swap(lt1[x],lt0[x]);
swap(rt1[x],rt0[x]);swap(tag0[x],tag1[x]);
s[x]=r-l+1-s[x];la2[x]^=1;
}
}
il void Pushdown(re int x,re int l,re int r)
{
re int mid=l+r>>1;
if(la0[x]) cover(ls,l,mid,0),cover(rs,mid+1,r,0);
if(la1[x]) cover(ls,l,mid,1),cover(rs,mid+1,r,1);
if(la2[x]) cover(ls,l,mid,2),cover(rs,mid+1,r,2);
la0[x]=la1[x]=la2[x]=0;
}
il void Modify(re int x,re int l,re int r,re int ql,re int qr,re int op)
{
if(tag1[x]&&op==1) return;
if(tag0[x]&&op==0) return;
if(ql<=l&&r<=qr) return cover(x,l,r,op);
re int mid=l+r>>1;
Pushdown(x,l,r);
if(ql<=mid) Modify(ls,l,mid,ql,qr,op);
if(qr>mid) Modify(rs,mid+1,r,ql,qr,op);
upd(x);
}
il int Query(re int x,re int l,re int r,re int ql,re int qr)
{
if(ql<=l&&r<=qr) return s[x];
re int mid=l+r>>1;
Pushdown(x,l,r);
if(qr<=mid) return Query(ls,l,mid,ql,qr);
if(ql>mid) return Query(rs,mid+1,r,ql,qr);
return Query(ls,l,mid,ql,qr)+Query(rs,mid+1,r,ql,qr);
}
il dat QueryS(re int x,re int l,re int r,re int ql,re int qr)
{
if(ql<=l&&r<=qr) return (dat){t1[x],lt1[x],rt1[x],tag1[x]};
re int mid=l+r>>1;
Pushdown(x,l,r);
if(qr<=mid) return QueryS(ls,l,mid,ql,qr);
if(ql>mid) return QueryS(rs,mid+1,r,ql,qr);
re dat A=QueryS(ls,l,mid,ql,qr),B=QueryS(rs,mid+1,r,ql,qr);
A.t1=max(A.t1,B.t1);
A.t1=max(A.t1,A.rt1+B.lt1);
if(A.tag1) A.lt1=A.lt1+B.lt1;
if(B.tag1) A.rt1=A.rt1+B.rt1;else A.rt1=B.rt1;
A.t1=max(A.t1,max(A.lt1,A.rt1));
A.tag1=A.tag1&B.tag1;
return A;
}
int main()
{
n=gi();m=gi();
Build(1,1,n);
re int gu=0;
while(m--)
{
re int op=gi(),l=gi()+1,r=gi()+1;
if(op<3) Modify(1,1,n,l,r,op);
if(op==3) printf("%d
",Query(1,1,n,l,r));
if(op==4) printf("%d
",QueryS(1,1,n,l,r).t1);
}
return 0;
}