线段树
pushdown写的很浪~
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 100000+10
using namespace std;
struct Node{
int L,R;
int tag;
int num[];
int lcon[],rcon[],mcon[];
Node(){
L=R=tag=;
num[]=num[]=;
lcon[]=rcon[]=mcon[]=;
lcon[]=rcon[]=mcon[]=;
}
}dat[MAXN<<];
int n,m;
int a[MAXN];
Node Merge(Node A,Node B){
if(A.L<)return B;
if(B.L<)return A;
Node ret;
ret.L=A.L,ret.R=B.R;
int ls=A.R-A.L,rs=B.R-B.L;
for(int i=;i<=;i++){
ret.num[i]=A.num[i]+B.num[i];
if(A.num[i]==ls)ret.lcon[i]=ls+B.lcon[i];
else ret.lcon[i]=A.lcon[i];
if(B.num[i]==rs)ret.rcon[i]=rs+A.rcon[i];
else ret.rcon[i]=B.rcon[i];
ret.mcon[i]=max(A.mcon[i],B.mcon[i]);
ret.mcon[i]=max(ret.mcon[i],A.rcon[i]+B.lcon[i]);
}
return ret;
}
void c(Node &A,int x){
x--;
int size=A.R-A.L;
A.num[x]=size,A.num[x^]=;
A.lcon[x]=A.rcon[x]=A.mcon[x]=size;
A.lcon[x^]=A.rcon[x^]=A.mcon[x^]=;
A.tag=x+;
}
void r(Node &A){
swap(A.num[],A.num[]);
swap(A.lcon[],A.lcon[]);
swap(A.rcon[],A.rcon[]);
swap(A.mcon[],A.mcon[]);
A.tag=;
}
void update(Node &A,int x){
if(x<=){c(A,x);return;}
if(!A.tag){
r(A);
}
else if(A.tag<=){
c(A,((A.tag-)^)+);
}
else{
r(A);
A.tag=;
}
}
void pushdown(int k){
if(!dat[k].tag)return;
update(dat[k<<],dat[k].tag);
update(dat[k<<|],dat[k].tag);
dat[k].tag=;
}
void build(int k,int L,int R){
if(L+==R){
dat[k].L=L,dat[k].R=R;
if(a[L]){dat[k].num[]=dat[k].lcon[]=dat[k].rcon[]=dat[k].mcon[]=;}
else {dat[k].num[]=dat[k].lcon[]=dat[k].rcon[]=dat[k].mcon[]=;}
return;
}
build(k<<,L,(L+R)>>);
build(k<<|,(L+R)>>,R);
dat[k]=Merge(dat[k<<],dat[k<<|]);
}
void rev(int a,int b,int k){
int L=dat[k].L,R=dat[k].R;
if(b<=L||R<=a){
return;
}
else if(a<=L&&R<=b){
update(dat[k],);
}
else{
pushdown(k);
rev(a,b,k<<);
rev(a,b,k<<|);
dat[k]=Merge(dat[k<<],dat[k<<|]);
}
}
void cha(int a,int b,int k,int x){
int L=dat[k].L,R=dat[k].R;
if(b<=L||R<=a){
return;
}
else if(a<=L&&R<=b){
update(dat[k],x);
}
else{
pushdown(k);
cha(a,b,k<<,x);
cha(a,b,k<<|,x);
dat[k]=Merge(dat[k<<],dat[k<<|]);
}
}
Node query(int a,int b,int k){
int L=dat[k].L,R=dat[k].R;
if(b<=L||R<=a){
Node ret;ret.L=-;
return ret;
}
else if(a<=L&&R<=b){
return dat[k];
}
else{
pushdown(k);
Node lc=query(a,b,k<<);
Node rc=query(a,b,k<<|);
return Merge(lc,rc);
}
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
build(,,n+);
int opt,x,y;
while(m--){
scanf("%d%d%d",&opt,&x,&y);x++,y++;
if(==opt||opt==){
cha(x,y+,,opt+);
}
else if(==opt){
rev(x,y+,);
}
else{
Node ans=query(x,y+,);
printf("%d\n",(==opt?ans.num[]:ans.mcon[]));
}
}
return ;
}