每日归档： 2018年11月8日

操作要求：
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
我们考虑维护线段树来处理这些询问。
考虑线段树的基本性质。线段树的特性决定了它能够\(O(nlogn)\)来处理各种能够\(O(1)\)合并两个子区间信息的信息。
上述询问中，总共有多少个1是很容易可以维护的。最大的问题在于维护“最多有多少个连续的1”
实际上，对于这里的每一种信息，我们都需要对称地维护它们——即，在维护1的信息的同时也要维护0的信息。这是操作\(2\)导致的。
我们考虑对于两种询问分别考虑。
首先是\(3\)，这个很好维护，直接维护\(1\)的个数即可。合并的时候简单相加即可。
对于\(4\)，第一个想到的肯定是可以维护区间的最长连续1。
但是我们发现，仅仅维护这个信息还是不够的。因为这样是无法把子区间的信息合并的。
我们反过来考虑，对于一个区间，它的最长连续1有可能怎样从两个子区间转移过来。
首先，可能是完全被包含在两个区间之一。这种情况的话，只需要维护区间的最长连续1，然后取Max即可。
但是，还有可能这个区间是跨越了两个区间的。这时候我们需要维护，子区间左起最长连续1与右起最长连续1。
然后，在转移区间信息的时候，我们只需要再考虑两个子区间的左起最长连续1与右起最长连续1即可。
接着我们考虑对于端点起最长连续1的转移——这种转移存在一种特殊情况，也就是，这个区间的端点起最长连续1的长度超过了中点。
这时候需要特殊判定。
这样就做完了。
写了5k，的确是一道麻题。

另，我莫名其妙RE了，估计是不知道哪里边界判挂了。考试的时候要注意在不MLE的情况下多开几倍的数组保险。

#include<iostream>
#include<cstdio>

#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
int n,m,a[100005],A,B,op;
inline int Max(int AA,int BB){
    return AA>BB?AA:BB;
}
struct data{ 
    int sm0;int sm1;
    int mx0;int mx1;
    int lmx0;int lmx1;
    int rmx0;int rmx1;
    //有翻转标记为1，否则为0；没有赋值为-1，有为0或1； 
    int lzy;int st;
    data(int sm0=0,int sm1=0,int mx0=0,int mx1=0,int lmx0=0,int lmx1=0,int rmx0=0,int rmx1=0,int lzy=0,int st=-1):
        sm0(sm0),sm1(sm1),mx0(mx0),mx1(mx1),lmx0(lmx0),lmx1(lmx1),rmx0(rmx0),rmx1(rmx1),lzy(lzy),st(st){}
}tr[300005];//262144
inline data mrg(const data &X,const data &Y,const data BS){
    data RT;
    RT.mx0=Max(X.mx0,Y.mx0);
    RT.mx0=Max(RT.mx0,X.rmx0+Y.lmx0);
    RT.sm0=X.sm0+Y.sm0;
    //一个巧妙的技巧，如果存在1，那么肯定不是全0，反之亦然。 
    RT.lmx0=X.sm1?X.lmx0:X.lmx0+Y.lmx0;
    RT.rmx0=Y.sm1?Y.rmx0:Y.rmx0+X.rmx0;
    
    RT.mx1=Max(X.mx1,Y.mx1);
    RT.mx1=Max(RT.mx1,X.rmx1+Y.lmx1);
    RT.sm1=X.sm1+Y.sm1;
    RT.lmx1=X.sm0?X.lmx1:X.lmx1+Y.lmx1;
    RT.rmx1=Y.sm0?Y.rmx1:Y.rmx1+X.rmx1;
    RT.lzy=BS.lzy;RT.st=BS.st;
    return RT;
}
inline void updt(int X){
    tr[X]=mrg(tr[LS],tr[RS],tr[X]);
}
inline void rnw1(int X,int L,int R){
    std::swap(tr[X].lmx0,tr[X].lmx1);
    std::swap(tr[X].rmx0,tr[X].rmx1);
    std::swap(tr[X].mx0,tr[X].mx1);
    std::swap(tr[X].sm0,tr[X].sm1);
}
inline void rnw20(int X,int L,int R){
    tr[X].lmx0=LEN;tr[X].lmx1=0;
    tr[X].rmx0=LEN;tr[X].rmx1=0;
    tr[X].mx0=LEN;tr[X].mx1=0;
    tr[X].sm0=LEN;tr[X].sm1=0;
}
inline void rnw21(int X,int L,int R){
    tr[X].lmx0=0;tr[X].lmx1=LEN;
    tr[X].rmx0=0;tr[X].rmx1=LEN;
    tr[X].mx0=0;tr[X].mx1=LEN;
    tr[X].sm0=0;tr[X].sm1=LEN;
}
inline void rnw(int X,int L,int R,int TYP){
    if(TYP==0){
        tr[X].lzy=0;tr[X].st=0;
        rnw20(X,L,R);
    }else if(TYP==1){
        tr[X].lzy=0;tr[X].st=1;
        rnw21(X,L,R);
    }else{
        tr[X].lzy^=1;
        rnw1(X,L,R);
    }
}
inline void pshd(int X,int L,int R){
    if(tr[X].st>-1){
        rnw(LS,L,MID,tr[X].st);rnw(RS,MID+1,R,tr[X].st);
        tr[X].st=-1;
    }
    if(tr[X].lzy){
        rnw(LS,L,MID,2);rnw(RS,MID+1,R,2);
        tr[X].lzy=0;
    }
}
inline void chg(int X,int L,int R,int TYP){
    if(A<=L&&R<=B){
        //如果完全被包含则直接更新。 
        rnw(X,L,R,TYP);
        return;
    }
    pshd(X,L,R);
    if(A<=MID){
        chg(LS,L,MID,TYP);
    }
    if(B>MID){
        chg(RS,MID+1,R,TYP);
    }
    updt(X);
}
inline data qry(int X,int L,int R){
    if(A<=L&&R<=B){
        pshd(X,L,R);
        return tr[X];
    }
    pshd(X,L,R);
    if(A<=MID){
        if(B>MID){
            return mrg(qry(LS,L,MID),qry(RS,MID+1,R),data());
        }else{
            return qry(LS,L,MID);
        }
    }else{
        if(B>MID){
            return qry(RS,MID+1,R);
        }else{
            return data();
        }
    }
}

inline void build(int X,int L,int R){
    if(L==R){
        tr[X]=(data){a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],0,-1};
        return;
    }
    build(LS,L,MID);
    build(RS,MID+1,R);
    updt(X);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    data ans;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&op,&A,&B);
        ++A,++B;
        if(op<3){
            chg(1,1,n,op);
        }else if(op==3||op==4){
            ans=qry(1,1,n);
            if(op==3){
                printf("%d\n",ans.sm1);
            }else if(op==4){
                printf("%d\n",ans.mx1);
            }
        }
    }
}
int main(){
    init();
    return 0;
}