yyz1005 @ 2023-03-14 13:44:16
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 100010;
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
ll n,m;
ll lco1[N<<2],rco1[N<<2];//左右连续1
ll lco0[N<<2],rco0[N<<2];//左右连续0
ll cnt1[N<<2],cnt0[N<<2];
ll sr1[N<<2],sr0[N<<2];
bool axo[N<<2];//区间异或次数
ll aco[N<<2]/*区间覆盖 0=无 -1->0 1=->1*/,a[N];
void pushup(ll id,ll l,ll r){
ll mid = (l+r)>>1;
lco0[id] = (lco0[lson(id)]==(mid-l+1)?lco0[lson(id)]+lco0[rson(id)]:lco0[lson(id)]);
rco0[id] = (rco0[rson(id)]==(r-mid)?rco0[rson(id)]+rco0[lson(id)]:rco0[rson(id)]);
lco1[id] = (lco1[lson(id)]==(mid-l+1)?lco1[lson(id)]+lco1[rson(id)]:lco1[lson(id)]);
rco1[id] = (rco1[rson(id)]==(r-mid)?rco1[rson(id)]+rco1[lson(id)]:rco1[rson(id)]);
cnt1[id] = cnt1[lson(id)]+cnt1[rson(id)];
cnt0[id] = cnt0[lson(id)]+cnt0[rson(id)];
sr1[id] = max(max(sr1[lson(id)],sr1[rson(id)]),rco1[lson(id)]+lco1[rson(id)]);
sr0[id] = max(max(sr0[lson(id)],sr0[rson(id)]),rco0[lson(id)]+lco0[rson(id)]);
}
void build(ll id,ll l,ll r){
if(l==r){
lco1[id] = (a[l]==1);
rco1[id] = (a[l]==1);
lco0[id] = (a[l]==0);
rco0[id] = (a[l]==0);
cnt1[id] = (a[l]==1);
cnt0[id] = (a[l]==0);
sr1[id] = (a[l]==1);
sr0[id] = (a[l]==0);
aco[id] = 0;
axo[id] = 0;
return;
}
ll mid = (l+r)>>1;
build(lson(id),l,mid);
build(rson(id),mid+1,r);
pushup(id,l,r);
}
void pushdown(ll id,ll l,ll r){
if(aco[id]==0){
if(axo[id]==0) return;
else {
axo[lson(id)]^=1;
axo[rson(id)]^=1;
axo[id] = 0;
swap(lco1[id],lco0[id]);
swap(rco1[id],rco0[id]);
swap(cnt1[id],cnt0[id]);
swap(sr1[id],sr0[id]);
}
} else {
aco[lson(id)] = aco[id];
axo[lson(id)] = 0;
aco[rson(id)] = aco[id];
axo[rson(id)] = 0;
if(aco[id]==1){
lco1[id] = r-l+1;
rco1[id] = r-l+1;
lco0[id] = 0;
rco0[id] = 0;
cnt1[id] = r-l+1;
cnt0[id] = 0;
sr1[id] = r-l+1;
sr0[id] = 0;
} else {
lco1[id] = 0;
rco1[id] = 0;
lco0[id] = r-l+1;
rco0[id] = r-l+1;
cnt0[id] = r-l+1;
cnt1[id] = 0;
sr1[id] = 0;
sr0[id] = r-l+1;
}
}
}
void QuerySet(ll id,ll l,ll r,ll ql,ll qr,bool val){
pushdown(id,l,r);
if(ql<=l&&r<=qr){
axo[id] = 0;
aco[id] = (val?1:-1);
if(val){
lco1[id] = r-l+1;
rco1[id] = r-l+1;
lco0[id] = 0;
rco0[id] = 0;
cnt1[id] = r-l+1;
cnt0[id] = 0;
sr1[id] = r-l+1;
sr0[id] = 0;
} else {
lco1[id] = 0;
rco1[id] = 0;
lco0[id] = r-l+1;
rco0[id] = r-l+1;
cnt0[id] = r-l+1;
cnt1[id] = 0;
sr1[id] = 0;
sr0[id] = r-l+1;
}
return;
}
ll mid = (l+r)>>1;
if(ql<=mid) QuerySet(lson(id),l,mid,ql,qr,val);
if(qr>=mid+1) QuerySet(rson(id),mid+1,r,ql,qr,val);
pushup(id,l,r);
}
void QueryXor(ll id,ll l,ll r,ll ql,ll qr){
pushdown(id,l,r);
if(ql<=l&&r<=qr){
if(aco[id]==1){
aco[id] = -1;
lco1[id] = 0;
rco1[id] = 0;
lco0[id] = r-l+1;
rco0[id] = r-l+1;
cnt0[id] = r-l+1;
cnt1[id] = 0;
sr1[id] = 0;
sr0[id] = r-l+1;
} else if (aco[id]==-1){
aco[id] = 1;
lco1[id] = r-l+1;
rco1[id] = r-l+1;
lco0[id] = 0;
rco0[id] = 0;
cnt1[id] = r-l+1;
cnt0[id] = 0;
sr1[id] = r-l+1;
sr0[id] = 0;
} else {
axo[id]^=1;
swap(lco1[id],lco0[id]);
swap(rco1[id],rco0[id]);
swap(cnt1[id],cnt0[id]);
swap(sr1[id],sr0[id]);
}
return;
}
ll mid = (l+r)>>1;
if(ql<=mid) QueryXor(lson(id),l,mid,ql,qr);
if(qr>=mid+1) QueryXor(rson(id),mid+1,r,ql,qr);
pushup(id,l,r);
}
ll QuerySum(ll id,ll l,ll r,ll ql,ll qr){
pushdown(id,l,r);
//printf("AskSum(%lld->%lld),Dfs(%lld->%lld)\n",ql,qr,l,r);
if(ql<=l&&r<=qr) /*{printf("an arry,%lld->%lld,sum = %lld;\n",l,r,cnt1[id]);*/return cnt1[id];/*}*/
ll mid = (l+r)>>1;
ll res = 0;
if(ql<=mid) res+=QuerySum(lson(id),l,mid,ql,qr);
if(qr>=mid+1) res+=QuerySum(rson(id),mid+1,r,ql,qr);
pushup(id,l,r);
//printf("AskSum(%lld->%lld),Dfs(%lld->%lld),res = %lld\n",ql,qr,l,r,res);
return res;
}
ll QuerySr1(ll id,ll l,ll r,ll ql,ll qr){
pushdown(id,l,r);
if(ql<=l&&r<=qr) return sr1[id];
ll mid = (l+r)>>1;
ll res = 0;
if(ql<=mid&&qr<=mid){
//在左半部分
res = QuerySr1(lson(id),l,mid,ql,qr);
} else if(ql>=mid+1&&qr>=mid+1){
//在左半部分
res = QuerySr1(lson(id),mid+1,r,ql,qr);
} else {
res = max(QuerySr1(lson(id),l,mid,ql,mid),QuerySr1(rson(id),mid+1,r,mid+1,qr));
ll ls1,rs1;
ls1 = rco1[lson(id)],rs1 = lco1[rson(id)];
ls1 = min(ls1,mid-ql+1),rs1 = min(rs1,qr-mid);
res = max(res,ls1+rs1);
}
pushup(id,l,r);
return res;
}
int main(){
//freopen("answer.txt","w",stdout);
scanf("%lld%lld",&n,&m);
for(ll i = 1; i <= n; i++) scanf("%lld",&a[i]);
build(1,1,n);
while(m--){
ll op,l,r;
scanf("%lld%lld%lld",&op,&l,&r);
l++,r++;
if(op==0) QuerySet(1,1,n,l,r,0);
if(op==1) QuerySet(1,1,n,l,r,1);
if(op==2) QueryXor(1,1,n,l,r);
if(op==3) printf("%lld\n",QuerySum(1,1,n,l,r));
if(op==4) printf("%lld\n",QuerySr1(1,1,n,l,r));
}
return 0;
}