我可以铭记一生的蛇皮线段树

左左右右上上下下中间两头

咳咳，没什么好说的了，开始写吧。

我，可真是，写了zz三天。

#include 
    
     #include 
     
      #include
      
       using namespace std;struct ANS {    int l, r, ans, len;    ANS(int a=0, int b = 0, int c = 0, int d = 0) : l(a), r(b), ans(c), len(d) {}};int n, q,a[4000101];int sum[4000101], l1[4000101], r1[4000101], l0[4000101], r0[4000101];int lg1[4000101], lg0[4000101],add1[4000101], add2[4000101];void pushup(int rt, int l, int r){    int mid = l + r>>1;        sum[rt] = sum[rt<<1] + sum[rt<<1|1];    l1[rt] = l1[rt<<1], r1[rt] = r1[rt<<1|1];    if(l1[rt]==mid-l + 1) l1[rt] += l1[rt<<1|1];    if(r1[rt]==r-mid) r1[rt] += r1[rt<<1];    l0[rt]=l0[rt<<1], r0[rt] = r0[rt<<1|1];    if(l0[rt]==mid-l + 1) l0[rt] += l0[rt<<1|1];    if(r0[rt] == r - mid) r0[rt] += r0[rt<<1];    lg1[rt]=max(max(lg1[rt<<1],lg1[rt<<1|1]),r1[rt<<1]+l1[rt<<1|1]);    lg0[rt]=max(max(lg0[rt<<1], lg0[rt<<1|1]),r0[rt<<1]+l0[rt<<1|1]);}void pushdown(int rt, int ln, int rn){    if(add1[rt]!=-1){        int c=add1[rt];        add2[rt<<1]=0;add1[rt<<1]=c;        sum[rt<<1]=ln*c;        l1[rt<<1]=r1[rt<<1]=lg1[rt<<1]=c?ln:0;        l0[rt<<1]=r0[rt<<1]=lg0[rt<<1]=c?0:ln;                c=add1[rt];        add2[rt<<1|1]=0;add1[rt<<1|1]=c;        sum[rt<<1|1]=rn*c;        l1[rt<<1|1]=r1[rt<<1|1]=lg1[rt<<1|1]=c?rn:0;        l0[rt<<1|1]=r0[rt<<1|1]=lg0[rt<<1|1]=c?0:rn;                add1[rt] = -1;    }    if(add2[rt]){        add2[rt<<1]^=1;        sum[rt<<1]=ln-sum[rt<<1];        swap(lg1[rt<<1],lg0[rt<<1]);        swap(l1[rt<<1],l0[rt<<1]);        swap(r1[rt<<1],r0[rt<<1]);                add2[rt<<1|1]^=1;        sum[rt<<1|1]=rn-sum[rt<<1|1];        swap(lg1[rt<<1|1],lg0[rt<<1|1]);        swap(l1[rt<<1|1],l0[rt<<1|1]);        swap(r1[rt<<1|1],r0[rt<<1|1]);                add2[rt] = 0;    }}void build(int rt, int l, int r) {    add1[rt] = -1, add2[rt] = 0;    if(l==r){        sum[rt]=a[l];        l1[rt]=r1[rt]=lg1[rt]=a[l];        l0[rt]=r0[rt]=lg0[rt]=!a[l];        return ;    }    int mid =l + r >> 1;    build(rt<<1,l,mid);    build(rt<<1|1,mid+1,r);    pushup(rt,l,r);}void modify(int rt, int l, int r, int L, int R, int c) {    if(L <= l && r <= R) {        add1[rt] = c;        add2[rt]=0;        sum[rt]=(r-l+1)*c;        l1[rt]=r1[rt]=lg1[rt]=c?(r-l+1):0;        l0[rt]=r0[rt]=lg0[rt]=c?0:(r - l +1);        return ;    }    int mid=l+r>>1;    pushdown(rt,mid-l+1,r-mid);    if(mid>=L)modify(rt<<1,l,mid,L,R,c);    if(mid
       
        <<1|1,mid+1,r,L,R,c);    pushup(rt,l,r);}void reverse_(int rt, int l, int r, int L, int R) {    if(L<=l&&r<=R){        add2[rt]^=1;        sum[rt]=(r-l+1)-sum[rt];        swap(lg1[rt],lg0[rt]);        swap(l1[rt],l0[rt]);        swap(r1[rt],r0[rt]);    return;    }    int mid=l+r>>1;    pushdown(rt,mid-l+1,r-mid);    if(mid>=L)reverse_(rt << 1,l,mid, L, R);    if(mid
        
         << 1 | 1, mid + 1, r, L, R);    pushup(rt, l, r);}int query1(int rt, int l, int r,int L, int R){    if(L<=l&& r<=R)return sum[rt];    int mid =l+r>>1;    pushdown(rt,mid-l+1,r-mid);    int ans=0;    if(mid>=L)ans+=query1(rt << 1, l, mid, L, R);    if(mid
         
          << 1 | 1, mid + 1, r, L, R); return ans;}ANS query2(int rt, int l, int r, int L, int R) { if(L == l && r == R) return ANS(l1[rt], r1[rt], lg1[rt], r - l + 1); int mid = l + r >> 1; pushdown(rt,mid-l+1,r-mid); if(R <= mid)return query2(rt << 1, l, mid, L, R); if(L > mid)return query2(rt << 1 | 1, mid + 1, r, L, R); ANS al=query2(rt << 1,l,mid,L,mid); ANS ar=query2(rt<<1 | 1, mid+1,r,mid+1, R); return ANS((al.l==al.len?al.l+ar.l:al.l),(ar.r == ar.len?ar.r+al.r:ar.r),max(max(al.ans,ar.ans),al.r+ar.l),al.len+ar.len);//全场最坑 }int main() { scanf("%d%d", &n, &q); for(int i = 1; i <= n;i++) scanf("%d", &a[i]); build(1, 1, n); while(q--){ int opt,x,y; scanf("%d%d%d",&opt,&x,&y); ++x,++y; if(opt==0)modify(1, 1, n, x, y, 0); if(opt==1)modify(1,1,n,x,y,1); if(opt==2)reverse_(1, 1, n, x, y); if(opt ==3)printf("%d\n", query1(1, 1, n, x, y)); if(opt == 4)printf("%d\n", query2(1, 1, n, x, y).ans); } return 0;}