题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1858
线段树维护序列，然后注意标记的合并处理就可以了。
代码：
cf1b9d16fdfaaf51e652cdbe8e5494eef01f7a79.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100010
#define INF 0x7fffffff
struct node {
int l,r,lmax0,max0,rmax0,lmax1,max1,rmax1,sum0,sum1;
bool flag0,flag1,flag2;
bool full0() {
return sum0==(r-l+1);
}
bool full1() {
return sum1==(r-l+1);
}
node () {
flag0=flag1=flag2=false;
}
} tree[MAXN*5];
int a[MAXN],n,m;
void inf(int t) {
if (tree[t].flag0) {
tree[t].sum0=tree[t].lmax0=tree[t].rmax0=tree[t].max0=tree[t].r-tree[t].l+1;
tree[t].sum1=tree[t].lmax1=tree[t].rmax1=tree[t].max1=0;
}
if (tree[t].flag1) {
tree[t].sum0=tree[t].lmax0=tree[t].rmax0=tree[t].max0=0;
tree[t].sum1=tree[t].lmax1=tree[t].rmax1=tree[t].max1=tree[t].r-tree[t].l+1;
}
if (tree[t].flag2) {
swap(tree[t].sum0,tree[t].sum1);
swap(tree[t].max0,tree[t].max1);
swap(tree[t].lmax0,tree[t].lmax1);
swap(tree[t].rmax0,tree[t].rmax1);
}
}
void sign0(int t) {
tree[t].flag1=tree[t].flag2=false;
tree[t].flag0=true;
inf(t);
}
void sign1(int t) {
tree[t].flag0=tree[t].flag2=false;
tree[t].flag1=true;
inf(t);
}
void sign2(int t) {
if ((!tree[t].flag0)&&(!tree[t].flag1)) {
inf(t);
tree[t].flag2^=true;
inf(t);
} else {
tree[t].flag2=false;
swap(tree[t].flag0,tree[t].flag1);
inf(t);
}
}
void pushdown(int t) {
if (tree[t].l<tree[t].r) {
if (tree[t].flag0) {
sign0(t<<1),sign0((t<<1)^1);
tree[t].flag0=false;
}
if (tree[t].flag1) {
sign1(t<<1),sign1((t<<1)^1);
tree[t].flag1=false;
}
if (tree[t].flag2) {
sign2(t<<1),sign2((t<<1)^1);
tree[t].flag2=false;
}
}
}
void update(int t) {
pushdown(t);
if (tree[t].l<tree[t].r) {
tree[t].sum0=tree[t<<1].sum0+tree[(t<<1)^1].sum0;
tree[t].sum1=tree[t<<1].sum1+tree[(t<<1)^1].sum1;
tree[t].lmax0=tree[t<<1].lmax0+(tree[t<<1].full0()?tree[(t<<1)^1].lmax0:0);
tree[t].rmax0=tree[(t<<1)^1].rmax0+(tree[(t<<1)^1].full0()?tree[t<<1].rmax0:0);
tree[t].lmax1=tree[t<<1].lmax1+(tree[t<<1].full1()?tree[(t<<1)^1].lmax1:0);
tree[t].rmax1=tree[(t<<1)^1].rmax1+(tree[(t<<1)^1].full1()?tree[t<<1].rmax1:0);
tree[t].max0=max(max(tree[t<<1].max0,tree[(t<<1)^1].max0),tree[t<<1].rmax0+tree[(t<<1)^1].lmax0);
tree[t].max1=max(max(tree[t<<1].max1,tree[(t<<1)^1].max1),tree[t<<1].rmax1+tree[(t<<1)^1].lmax1);
}
}
void build(int l,int r,int t) {
tree[t].l=l,tree[t].r=r;
if (l==r) {
tree[t].sum0=tree[t].lmax0=tree[t].max0=tree[t].rmax0=a[l]==0?1:0;
tree[t].sum1=tree[t].lmax1=tree[t].max1=tree[t].rmax1=a[l]==1?1:0;
return ;
}
build(l,(l+r)>>1,t<<1),build(((l+r)>>1)+1,r,(t<<1)^1);
update(t);
}
void change0(int l,int r,int t) {
pushdown(t);
if (tree[t].l==l&&tree[t].r==r) {
sign0(t);
return ;
}
int mid=(tree[t].l+tree[t].r)>>1;
if (r<=mid) change0(l,r,t<<1); else if (l>mid) change0(l,r,(t<<1)^1)
; else change0(l,mid,t<<1),change0(mid+1,r,(t<<1)^1);
update(t);
}
void change1(int l,int r,int t) {
pushdown(t);
if (tree[t].l==l&&tree[t].r==r) {
sign1(t);
return ;
}
int mid=(tree[t].l+tree[t].r)>>1;
if (r<=mid) change1(l,r,t<<1); else if (l>mid) change1(l,r,(t<<1)^1)
; else change1(l,mid,t<<1),change1(mid+1,r,(t<<1)^1);
update(t);
}
void change2(int l,int r,int t) {
pushdown(t);
if (tree[t].l==l&&tree[t].r==r) {
sign2(t);
return ;
}
int mid=(tree[t].l+tree[t].r)>>1;
if (r<=mid) change2(l,r,t<<1); else if (l>mid) change2(l,r,(t<<1)^1)
; else change2(l,mid,t<<1),change2(mid+1,r,(t<<1)^1);
update(t);
}
int query3(int l,int r,int t) {
pushdown(t);
if (tree[t].l==l&&r==tree[t].r) return tree[t].sum1;
int mid=(tree[t].l+tree[t].r)>>1;
if (r<=mid) return query3(l,r,t<<1); else if (l>mid) return query3(l,r,(t<<1)^1)
; else return query3(l,mid,t<<1)+query3(mid+1,r,(t<<1)^1);
}
struct ans_type {
int lmax,max,rmax,size;
ans_type (int _lmax,int _max,int _rmax,int _size):lmax(_lmax),max(_max),rmax(_rmax),size(_size) {
}
bool full() {
return lmax==size;
}
};
ans_type query4(int l,int r,int t) {
pushdown(t);
if (tree[t].l==l&&tree[t].r==r) return ans_type(tree[t].lmax1,tree[t].max1,tree[t].rmax1,r-l+1);
int mid=(tree[t].l+tree[t].r)>>1;
if (r<=mid) return query4(l,r,t<<1); else if (l>mid) return query4(l,r,(t<<1)^1)
; else {
ans_type lx=query4(l,mid,t<<1),rx=query4(mid+1,r,(t<<1)^1),x=ans_type(0,0,0,0);
x.lmax=lx.lmax+(lx.full()?rx.lmax:0);
x.rmax=rx.rmax+(rx.full()?lx.rmax:0);
x.max=max(max(lx.max,rx.max),lx.rmax+rx.lmax);
x.size=lx.size+rx.size;
return x;
}
}
int main() {
scanf("%d%d",&n,&m);
for (int i=0;i++<n;) scanf("%d",&a[i]);
build(1,n,1);
while (m--) {
int k,l,r;
scanf("%d%d%d",&k,&l,&r);
l++,r++;
switch (k) {
case 0:
change0(l,r,1);
break;
case 1:
change1(l,r,1);
break;
case 2:
change2(l,r,1);
break;
case 3:
printf("%d\n",query3(l,r,1));
break;
case 4:
printf("%d\n",query4(l,r,1).max);
break;
}
}
return 0;
}
