https://www.lydsy.com/JudgeOnline/problem.php?id=1858
线段树嘛，很裸的，正好趁自己神志不清试着来写写吧。
woc这线段树真恶心，2个标记维护7个量！
显然需要维护区间1个数，区间最大连续1。
为了合并还需要维护区间左最大连续1和右最大连续1.
为了取反还需要把上述东西的0也给求出来。
之后你愉快的敲起了数组线段树，结果发现你4操作写起来贼费劲。
靠！改结构体！
然后就是两个标记纠缠不清的问题了。
于是过了三次拍，debug了三次，终于过了……
2h+考场直接gg。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+;
const int p=1e9+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int l,r,ls0,rs0,ls1,rs1;
int lz,sum,rng0,rng1;
bool rev;
}t[N*];
int n,m,b[N];
inline void upt(int a,int l,int r){
int mid=(l+r)>>,ls=a<<,rs=a<<|;
t[a].sum=t[ls].sum+t[rs].sum;
t[a].rng1=max(t[ls].rs1+t[rs].ls1,max(t[ls].rng1,t[rs].rng1));
t[a].rng0=max(t[ls].rs0+t[rs].ls0,max(t[ls].rng0,t[rs].rng0));
t[a].ls1=t[ls].ls1+(t[ls].ls1==mid-l+?t[rs].ls1:);
t[a].rs1=t[rs].rs1+(t[rs].rs1==r-mid?t[ls].rs1:);
t[a].ls0=t[ls].ls0+(t[ls].ls0==mid-l+?t[rs].ls0:);
t[a].rs0=t[rs].rs0+(t[rs].rs0==r-mid?t[ls].rs0:);
}
inline void turn(int a){
t[a].sum=t[a].r-t[a].l+-t[a].sum;
swap(t[a].ls1,t[a].ls0);
swap(t[a].rs1,t[a].rs0);
swap(t[a].rng1,t[a].rng0);
}
inline void change(int a,int w){
if(w){
t[a].ls1=t[a].rs1=t[a].sum=t[a].rng1=t[a].r-t[a].l+;
t[a].ls0=t[a].rs0=t[a].rng0=;
}
else{
t[a].ls0=t[a].rs0=t[a].rng0=t[a].r-t[a].l+;
t[a].ls1=t[a].rs1=t[a].sum=t[a].rng1=;
}
t[a].rev=;
}
inline void push(int a){
int ls=a<<,rs=a<<|;
if(t[a].lz!=-){
change(ls,t[a].lz);change(rs,t[a].lz);
t[ls].lz=t[rs].lz=t[a].lz;t[a].lz=-;
}
if(t[a].rev){
turn(ls);turn(rs);
t[ls].rev^=;t[rs].rev^=;t[a].rev=;
}
}
void build(int a,int l,int r){
t[a].lz=-;t[a].rev=;t[a].l=l;t[a].r=r;
if(l==r){
t[a].sum=b[l];
if(b[l])t[a].ls1=t[a].rs1=t[a].rng1=;
else t[a].ls0=t[a].rs0=t[a].rng0=;
return;
}
int mid=(l+r)>>;
build(a<<,l,mid);build(a<<|,mid+,r);
upt(a,l,r);
}
void modify(int a,int l,int r,int l1,int r1,int w){
if(r<l1||r1<l)return;
if(l1<=l&&r<=r1){
t[a].lz=w;change(a,w);
return;
}
push(a);
int mid=(l+r)>>;
modify(a<<,l,mid,l1,r1,w);
modify(a<<|,mid+,r,l1,r1,w);
upt(a,l,r);
}
void reverse(int a,int l,int r,int l1,int r1){
if(r<l1||r1<l)return;
if(l1<=l&&r<=r1){
t[a].rev^=;turn(a);
return;
}
push(a);
int mid=(l+r)>>;
reverse(a<<,l,mid,l1,r1);
reverse(a<<|,mid+,r,l1,r1);
upt(a,l,r);
}
int query_sum(int a,int l,int r,int l1,int r1){
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)return t[a].sum;
push(a);
int mid=(l+r)>>;
return query_sum(a<<,l,mid,l1,r1)+
query_sum(a<<|,mid+,r,l1,r1);
}
node query_rng(int a,int l,int r,int l1,int r1){
if(l1==l&&r==r1)return t[a];
push(a);
int mid=(l+r)>>;
if(mid>=r1)return query_rng(a<<,l,mid,l1,r1);
else if(mid+<=l1)return query_rng(a<<|,mid+,r,l1,r1);
node lans=query_rng(a<<,l,mid,l1,mid);
node rans=query_rng(a<<|,mid+,r,mid+,r1);
node ans;
ans.l=lans.l;ans.r=rans.r;
ans.rng1=max(lans.rs1+rans.ls1,max(lans.rng1,rans.rng1));
ans.rng0=max(lans.rs0+rans.ls0,max(lans.rng0,rans.rng0));
ans.ls1=lans.ls1+(lans.ls1==mid-l+?rans.ls1:);
ans.rs1=rans.rs1+(rans.rs1==r-mid?lans.rs1:);
ans.ls0=lans.ls0+(lans.ls0==mid-l+?rans.ls0:);
ans.rs0=rans.rs0+(rans.rs0==r-mid?lans.rs0:);
return ans;
}
int main(){
n=read(),m=read();
for(int i=;i<=n;i++)b[i]=read();
build(,,n);
while(m--){
int op=read(),l=read()+,r=read()+;
if(op==)modify(,,n,l,r,);
if(op==)modify(,,n,l,r,);
if(op==)reverse(,,n,l,r);
if(op==)printf("%d\n",query_sum(,,n,l,r));
if(op==)printf("%d\n",query_rng(,,n,l,r).rng1);
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++