操作要求：
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;
}