K_J_M @ 2024-07-23 15:41:48
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n,m,op,l,r,a[N];
struct node{
int lmax1,rmax1,lmax0,rmax0,max0,max1,sum1,sum0,lazy0,lazy1,lazy2;
}b[N<<2];
void push_up(int p,int s,int t){
int ls=p<<1,rs=p<<1|1;
int mid=(s+t)>>1;
b[p].sum0=b[ls].sum0+b[rs].sum0;
b[p].sum1=b[ls].sum1+b[rs].sum1;
b[p].rmax1=max(b[rs].rmax1,b[rs].rmax1+(b[rs].rmax1==t-mid? 1:0)*(b[ls].rmax1));
b[p].rmax0=max(b[rs].rmax0,b[rs].rmax0+(b[rs].rmax0==t-mid? 1:0)*(b[ls].rmax0));
b[p].lmax1=max(b[ls].lmax1,b[ls].lmax1+(b[ls].lmax1==mid-s+1? 1:0)*(b[rs].lmax1));
b[p].lmax0=max(b[ls].lmax0,b[ls].lmax0+(b[ls].lmax0==mid-s+1? 1:0)*(b[rs].lmax0));
b[p].max0=max(max(b[ls].max0,b[rs].max0),b[ls].rmax0+b[rs].lmax0);
b[p].max1=max(max(b[ls].max1,b[rs].max1),b[ls].rmax1+b[rs].lmax1);
}
void push_down(int p,int s,int t){
int ls=p<<1,rs=p<<1|1;
int mid=(s+t)>>1;
if(b[p].lazy0){
b[p].lazy2=0;b[ls].lazy2=0;b[rs].lazy2=0;
b[ls].lazy0=b[rs].lazy0=1;
b[p].lazy0=0;
b[ls].lmax0=b[ls].rmax0=b[ls].max0=b[ls].sum0=mid-s+1;
b[ls].lmax1=b[ls].rmax1=b[ls].max1=b[ls].sum1=0;
b[rs].lmax0=b[rs].rmax0=b[rs].max0=b[rs].sum0=t-mid;
b[rs].lmax1=b[rs].rmax1=b[rs].max1=b[ls].sum1=0;
}
if(b[p].lazy1){
b[p].lazy2=0;b[ls].lazy2=0;b[rs].lazy2=0;
b[ls].lazy1=b[rs].lazy1=1;
b[p].lazy1=0;
b[ls].lmax0=b[ls].rmax0=b[ls].max0=b[ls].sum0=0;
b[ls].lmax1=b[ls].rmax1=b[ls].max1=b[ls].sum1=mid-s+1;
b[rs].lmax0=b[rs].rmax0=b[rs].max0=b[rs].sum0=0;
b[rs].lmax1=b[rs].rmax1=b[rs].max1=b[rs].sum1=t-mid;
}
if(b[p].lazy2){
swap(b[ls].lmax0,b[ls].lmax1);swap(b[ls].max0,b[ls].max1);
swap(b[ls].rmax0,b[ls].rmax1);swap(b[ls].sum0,b[ls].sum1);
swap(b[rs].lmax0,b[rs].lmax1);swap(b[rs].max0,b[rs].max1);
swap(b[rs].rmax0,b[rs].rmax1);swap(b[rs].sum0,b[rs].sum1);
if(b[ls].lazy1){
b[ls].lazy0=1;
b[ls].lazy1=0;
}else{
if(b[ls].lazy0){
b[ls].lazy1=1;
b[ls].lazy0=0;
}else{
b[ls].lazy2^=1;
}
}
if(b[rs].lazy1){
b[rs].lazy0=1;
b[rs].lazy1=0;
}else{
if(b[rs].lazy0){
b[rs].lazy1=1;
b[rs].lazy0=0;
}else{
b[rs].lazy2^=1;
}
}
b[p].lazy2=0;
}
}
void build(int p,int s,int t){
if(s==t){
b[p].lmax1=b[p].rmax1=b[p].sum1=b[p].max1=(a[s]==1? 1:0);
b[p].lmax0=b[p].rmax0=b[p].sum0=b[p].max0=(a[s]==0? 1:0);
return;
}
int mid=(s+t)>>1;
build(p<<1,s,mid);build(p<<1|1,mid+1,t);
push_up(p,s,t);
}
void update_0(int p,int s,int t,int ql,int qr){//全部变成0
if(t<=qr&&s>=ql){
int len=t-s+1;
b[p].lmax0=b[p].max0=b[p].rmax0=b[p].sum0=len;
b[p].lmax1=b[p].max1=b[p].rmax1=b[p].sum1=0;
b[p].lazy2=b[p].lazy1=0;
b[p].lazy0=1;
return;
}
if(t<ql||s>qr) return;
int mid=(s+t)>>1;
push_down(p,s,t);
update_0(p<<1,s,mid,ql,qr);
update_0(p<<1|1,mid+1,t,ql,qr);
push_up(p,s,t);
}
void update_1(int p,int s,int t,int ql,int qr){//全部变成1
if(t<=qr&&s>=ql){
int len=t-s+1;
b[p].lmax0=b[p].max0=b[p].rmax0=b[p].sum0=0;
b[p].lmax1=b[p].max1=b[p].rmax1=b[p].sum1=len;
b[p].lazy2=b[p].lazy0=0;
b[p].lazy1=1;
return;
}
if(t<ql||s>qr) return;
int mid=(s+t)>>1;
push_down(p,s,t);
update_1(p<<1,s,mid,ql,qr);
update_1(p<<1|1,mid+1,t,ql,qr);
push_up(p,s,t);
}
void update_2(int p,int s,int t,int ql,int qr){//取反
if(t<=qr&&s>=ql){
swap(b[p].lmax0,b[p].lmax1);swap(b[p].max0,b[p].max1);
swap(b[p].rmax0,b[p].rmax1);swap(b[p].sum0,b[p].sum1);
b[p].lazy2^=1;
return;
}
if(t<ql||s>qr) return;
int mid=(s+t)>>1;
push_down(p,s,t);
update_2(p<<1,s,mid,ql,qr);
update_2(p<<1|1,mid+1,t,ql,qr);
push_up(p,s,t);
}
int query_3(int p,int s,int t,int ql,int qr){//查询1的个数
push_down(p,s,t);
if(t<=qr&&s>=ql) return b[p].sum1;
if(t<ql||s>qr) return 0;
int mid=(s+t)>>1;
return query_3(p<<1,s,mid,ql,qr)+query_3(p<<1|1,mid+1,t,ql,qr);
}
int query_4(int p,int s,int t,int ql,int qr){
push_down(p,s,t);
if(s==ql&&t==qr) return b[p].max1;
int mid=(s+t)>>1;
if(mid>=qr) return query_4(p<<1,s,mid,ql,qr);
else if(mid<ql) return query_4(p<<1|1,mid+1,t,ql,qr);
else return max(max(query_4(p<<1,s,mid,ql,mid),query_4(p<<1|1,mid+1,t,mid+1,qr)),min(b[p<<1].rmax1,mid-ql+1)+min(b[p<<1|1].lmax1,qr-mid));
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--){
cin>>op>>l>>r;
l++,r++;
if(op==0) update_0(1,1,n,l,r);
if(op==1) update_1(1,1,n,l,r);
if(op==2) update_2(1,1,n,l,r);
if(op==3) cout<<query_3(1,1,n,l,r)<<endl;
if(op==4) cout<<query_4(1,1,n,l,r)<<endl;
}
return 0;
}
/*
0 l r 把 [l, r] 区间内的所有数全变成 0
1 l r 把 [l, r] 区间内的所有数全变成 1
2 l r 把 [l,r] 区间内的所有数全部取反，也就是说把所有的 0 变成 1把所有的 1变成 0
3 l r 询问 [l, r] 区间内总共有多少个 1
4 l r 询问 [l, r] 区间内最多有多少个连续的 1
10 5
1 1 1 1 1 1 1 1 1 1
2 0 9
3 0 9
4 0 9
2 0 5
3 0 9
*/阳历过了，求条，悬关