LYqwq @ 2023-11-07 21:07:24
rt QwQ
记录
#include <iostream>
#include <cstring>
using namespace std;
inline int read(){
int X=0; bool flag=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+(ch^48),ch=getchar();
if(flag) return X;
return ~(X-1);
}
inline void write(int X){
if(X<0) putchar('-'),X=~(X-1);
int s[20],top=0;
while(X) s[++top]=X%10,X/=10;
if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
putchar('\n');
}
const int N=1e5+5;
int n,m,op,l,r;
int a[N];
class SgT{
public:
struct node;
void build(int rt,int l,int r){
t[rt].l=l,t[rt].r=r,t[rt].len=r-l+1,t[rt].chg=0;
if(l==r){
t[rt].sum=t[rt].s1=t[rt].h1=t[rt].ct1=a[l];
t[rt].s0=t[rt].h0=t[rt].ct0=!a[l];
return;
}
int mid=l+r>>1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
pushup(rt);
}
void update(int rt,int l,int r,int tp){
pushdown(rt);
if(l<=t[rt].l && t[rt].r<=r){
upd(rt,tp);
// if(tp==0){
// t[rt].ct0=t[rt].s0=t[rt].h0=t[rt].len;
// t[rt].sum=t[rt].ct1=t[rt].s1=t[rt].h1=0;
// t[rt].chg=1,t[rt].xr=0;
// }else if(tp==1){
// t[rt].ct0=t[rt].s0=t[rt].h0=0;
// t[rt].sum=t[rt].ct1=t[rt].s1=t[rt].h1=t[rt].len;
// t[rt].chg=2,t[rt].xr=0;
// }else{
// t[rt].sum=t[rt].len-t[rt].sum;
// swap(t[rt].ct0,t[rt].ct1),swap(t[rt].s0,t[rt].s1),swap(t[rt].h0,t[rt].h1);
// if(t[rt].chg==1) t[rt].chg=2;
// else if(t[rt].chg==2) t[rt].chg=1;
// else t[rt].xr^=1;
// // t[rt].xr^=1;
// }
return;
}
int mid=t[rt].l+t[rt].r>>1;
if(l<=mid) update(ls(rt),l,r,tp);
if(r>mid) update(rs(rt),l,r,tp);
pushup(rt);
}
int querySum(int rt,int l,int r){
pushdown(rt);
if(l<=t[rt].l && t[rt].r<=r)
return t[rt].sum;
int res=0;
int mid=t[rt].l+t[rt].r>>1;
if(l<=mid) res+=querySum(ls(rt),l,r);
if(r>mid) res+=querySum(rs(rt),l,r);
return res;
}
int queryCt(int rt,int l,int r){
pushdown(rt);
if(l<=t[rt].l && t[rt].r<=r)
return t[rt].ct1;
int res=0;
int mid=t[rt].l+t[rt].r>>1;
if(r<=mid) res=queryCt(ls(rt),l,r);
else if(l>mid) res=queryCt(rs(rt),l,r);
else{
res=max(queryCt(ls(rt),l,mid),queryCt(rs(rt),mid+1,r));
res=max(res,min(t[ls(rt)].h1,mid-l+1)+min(t[rs(rt)].s1,r-mid));
}
return res;
}
struct node{
int l,r; // 左右端点
int len; // 长度=r-l+1
int s1,h1; // s1：以左端点开头最长连续 1 个数 h1：以右端点开头
int s0,h0; // s0：以左端点开头最长连续 0 个数 h0：以右端点开头
int ct1,ct0; // 最长连续 1 与最长连续 0
int sum; // 1 的总和
int chg; // 懒标记 1:变0 2:变1
int xr; // 取反懒标记
}t[N<<2];
inline int ls(int rt){return rt<<1;}
inline int rs(int rt){return rt<<1|1;}
inline void pushup(int rt){
int l=ls(rt),r=rs(rt);
t[rt].sum=t[l].sum+t[r].sum;
t[rt].s1=t[l].sum==t[l].len ? t[l].len+t[r].s1 : t[l].s1;
t[rt].h1=t[r].sum==t[r].len ? t[r].len+t[l].h1 : t[r].h1;
t[rt].ct1=max(max(t[l].ct1,t[r].ct1),t[l].h1+t[r].s1);
t[rt].s0=t[l].sum==t[l].len ? t[l].len+t[r].s0 : t[l].s0;
t[rt].h0=t[r].sum==t[r].len ? t[r].len+t[l].h0 : t[r].h0;
t[rt].ct0=max(max(t[l].ct0,t[r].ct0),t[l].h0+t[r].s0);
}
inline void upd(int rt,int tp){
if(tp==1){
t[rt].ct0=t[rt].s0=t[rt].h0=t[rt].len;
t[rt].sum=t[rt].ct1=t[rt].s1=t[rt].h1=0;
t[rt].chg=1,t[rt].xr=0;
}else if(tp==2){
t[rt].ct0=t[rt].s0=t[rt].h0=0;
t[rt].sum=t[rt].ct1=t[rt].s1=t[rt].h1=t[rt].len;
t[rt].chg=2,t[rt].xr=0;
}else if(tp==3){
t[rt].sum=t[rt].len-t[rt].sum;
swap(t[rt].ct0,t[rt].ct1);
swap(t[rt].s0,t[rt].s1),swap(t[rt].h0,t[rt].h1);
if(t[rt].chg==1) t[rt].chg=2;
else if(t[rt].chg==2) t[rt].chg=1;
else t[rt].xr^=1;
}
}
inline void pushdown(int rt){
upd(ls(rt),t[rt].chg ? t[rt].chg : t[rt].xr ? 3 : 0);
upd(rs(rt),t[rt].chg ? t[rt].chg : t[rt].xr ? 3 : 0);
t[rt].chg=t[rt].xr=0;
}
}t;
int main(){
n=read(),m=read();
for(int i=1; i<=n; i++) a[i]=read();
t.build(1,1,n);
while(m--){
op=read(),l=read()+1,r=read()+1;
if(0<=op && op<=2) t.update(1,l,r,op+1);
else if(op==3) write(t.querySum(1,l,r));
else write(t.queryCt(1,l,r));
}
return 0;
}