线段树神仙操作==珂朵莉树基本操作？？？
珂朵莉树是不可能的，这辈子只会码线段树，只有线段树神仙操作才刺激，debug之后AC才最快乐
这题我折腾了半个下午加半个晚上。维护的东西太多了。
如果没有区间反转，这题很简单，但是有反转，所以既要维护1，又要维护0。
tot记录区间中1的个数
len记录区间长度
l记录区间左端点
r记录区间右端点
sum1表示区间中最长连续的1的个数
lmax1表示区间中以左端点为起点从左往右的连续1的个数
rmax1表示区间中以右端点为起点从右往左的连续1的个数
0同理
laz1表示区间覆盖，0表示无操作，1表示0覆盖，2表示1覆盖
laz2表示区间反转，0表示无操作，1表示反转
先附上代码，有时间再填坑
#include<iostream> #include<cstdio> #define R register #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define ls k<<1 #define rs k<<1|1 #define mid ((l+r)>>1) #define sum1(rt) tr[rt].sum1 #define sum0(rt) tr[rt].sum0 #define lmax1(rt) tr[rt].lmax1 #define lmax0(rt) tr[rt].lmax0 #define rmax1(rt) tr[rt].rmax1 #define rmax0(rt) tr[rt].rmax0 #define len(rt) tr[rt].len #define laz1(rt) tr[rt].laz1 #define laz2(rt) tr[rt].laz2 #define tot(rt) tr[rt].tot #define l(rt) tr[rt].l #define r(rt) tr[rt].r using namespace std; const int maxn=200005; int n,m,a[maxn]; struct node{ int sum1,lmax1,rmax1; int tot,len,laz1,laz2,l,r; int sum0,lmax0,rmax0; }tr[maxn<<2]; inline int read(){ R int s=0,w=1; R char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } inline void update(R int k){ lmax1(k)=(sum1(ls)==len(ls))?len(ls)+lmax1(rs):lmax1(ls); rmax1(k)=(sum1(rs)==len(rs))?len(rs)+rmax1(ls):rmax1(rs); sum1(k)=max(max(sum1(ls),sum1(rs)),rmax1(ls)+lmax1(rs)); lmax0(k)=(sum0(ls)==len(ls))?len(ls)+lmax0(rs):lmax0(ls); rmax0(k)=(sum0(rs)==len(rs))?len(rs)+rmax0(ls):rmax0(rs); sum0(k)=max(max(sum0(ls),sum0(rs)),rmax0(ls)+lmax0(rs)); tot(k)=tot(ls)+tot(rs); } void build(R int k,R int l,R int r){ len(k)=r-l+1;l(k)=l;r(k)=r; if(l==r){ tot(k)=a[l]; lmax1(k)=rmax1(k)=sum1(k)=((a[l]==1)?1:0); lmax0(k)=rmax0(k)=sum0(k)=((a[l]==1)?0:1); return ; } build(lson);build(rson); update(k); } inline void down(R int k){ if(laz1(k)==1){ sum0(ls)=lmax0(ls)=rmax0(ls)=len(ls); tot(ls)=sum1(ls)=lmax1(ls)=rmax1(ls)=0; laz1(ls)=1;laz2(ls)=0; sum0(rs)=lmax0(rs)=rmax0(rs)=len(rs); tot(rs)=sum1(rs)=lmax1(rs)=rmax1(rs)=0; laz1(rs)=1;laz2(rs)=0; laz1(k)=0;laz2(k)=0; } if(laz1(k)==2){ tot(ls)=sum1(ls)=lmax1(ls)=rmax1(ls)=len(ls); sum0(ls)=lmax0(ls)=rmax0(ls)=0; laz1(ls)=2;laz2(ls)=0; tot(rs)=sum1(rs)=lmax1(rs)=rmax1(rs)=len(rs); sum0(rs)=lmax0(rs)=rmax0(rs)=0; laz1(rs)=2;laz2(rs)=0; laz1(k)=0;laz2(k)=0; } if(laz2(k)){ tot(ls)=len(ls)-tot(ls); swap(sum0(ls),sum1(ls)); swap(lmax0(ls),lmax1(ls)); swap(rmax0(ls),rmax1(ls)); if(laz1(ls)==1)laz1(ls)=2; else if(laz1(ls)==2)laz1(ls)=1; else laz2(ls)^=1; tot(rs)=len(rs)-tot(rs); swap(sum0(rs),sum1(rs)); swap(lmax0(rs),lmax1(rs)); swap(rmax0(rs),rmax1(rs)); if(laz1(rs)==1)laz1(rs)=2; else if(laz1(rs)==2)laz1(rs)=1; else laz2(rs)^=1; laz2(k)=0; } } void change(R int k,R int l,R int r,R int x,R int y,R int z){ // printf("?%d %d?\n",l,r); down(k); if(l==x&&y==r){ if(z==1){ sum0(k)=lmax0(k)=rmax0(k)=len(k); tot(k)=sum1(k)=lmax1(k)=rmax1(k)=0; laz1(k)=1; laz2(k)=0; } else if(z==2){ tot(k)=sum1(k)=lmax1(k)=rmax1(k)=len(k); sum0(k)=lmax0(k)=rmax0(k)=0; laz1(k)=2; laz2(k)=0; } else { tot(k)=len(k)-tot(k); swap(sum0(k),sum1(k)); swap(lmax0(k),lmax1(k)); swap(rmax0(k),rmax1(k)); laz2(k)^=1; } return ; } if(y<=mid)change(lson,x,y,z); else if(x>mid)change(rson,x,y,z); else change(lson,x,mid,z),change(rson,mid+1,y,z); update(k); } int ask1(R int k,R int l,R int r,R int x,R int y){ down(k); if(l==x&&y==r){ return tot(k); } if(y<=mid)return ask1(lson,x,y); else if(x>mid)return ask1(rson,x,y); else return ask1(lson,x,mid)+ask1(rson,mid+1,y); } node ask2(R int k,R int l,R int r,R int x,R int y){ down(k); if(l==x&&y==r){ return tr[k]; } if(y<=mid)return ask2(lson,x,y); else if(x>mid)return ask2(rson,x,y); else { node tl=ask2(lson,x,mid),tr=ask2(rson,mid+1,y),tmp; tmp.l=tl.l; tmp.r=tr.r; tmp.lmax1=(tl.tot==tl.len)?tl.tot+tr.lmax1:tl.lmax1; tmp.rmax1=(tr.tot==tr.len)?tr.tot+tl.rmax1:tr.rmax1; tmp.sum1=max(tl.sum1,max(tr.sum1,tl.rmax1+tr.lmax1)); return tmp; } } int main(){ n=read();m=read(); for(R int i=1;i<=n;++i) a[i]=read(); build(1,1,n); int opt,a,b; while(m--){ opt=read();a=read()+1;b=read()+1; if(opt==0)change(1,1,n,a,b,1); else if(opt==1)change(1,1,n,a,b,2); else if(opt==2)change(1,1,n,a,b,3); else if(opt==3)printf("%d\n",ask1(1,1,n,a,b)); else if(opt==4)printf("%d\n",ask2(1,1,n,a,b).sum1); } return 0; }