题目链接
比之前那个区间最多公约数简单,结构体里维护一下区间0,1的个数,区间最长0,1连续串长度,区间左右端点最长连续0,1串长度即可,0,1都维护是为了翻转操作。
对于翻转标记的lz数组需要分类讨论,对于合并区间的时候跨区间要单独讨论。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
//#define int long long
//const ll P=2281701377;
const ll P=998244353;
const int mod=1e9+7;
#define fi first
#define se second
struct node{
int cnt[2];
int maxx[2];
int pre[2],nex[2];
}tree[N*4];
int n,m;
int a[N];
int lz[N*4];
void pushup(int p,int l,int r){
int mid=(l+r)>>1;
tree[p].cnt[0]=tree[p<<1].cnt[0]+tree[p<<1|1].cnt[0];
tree[p].cnt[1]=tree[p<<1].cnt[1]+tree[p<<1|1].cnt[1];
tree[p].maxx[0]=max(tree[p<<1].maxx[0],tree[p<<1|1].maxx[0]);
tree[p].maxx[0]=max(tree[p].maxx[0],tree[p<<1].nex[0]+tree[p<<1|1].pre[0]);
tree[p].maxx[1]=max(tree[p<<1].maxx[1],tree[p<<1|1].maxx[1]);
tree[p].maxx[1]=max(tree[p].maxx[1],tree[p<<1].nex[1]+tree[p<<1|1].pre[1]);
tree[p].pre[0]=tree[p<<1].pre[0];
if(tree[p<<1].pre[0]==mid-l+1)
tree[p].pre[0]+=tree[p<<1|1].pre[0];
tree[p].pre[1]=tree[p<<1].pre[1];
if(tree[p<<1].pre[1]==mid-l+1)
tree[p].pre[1]+=tree[p<<1|1].pre[1];
tree[p].nex[0]=tree[p<<1|1].nex[0];
if(tree[p<<1|1].nex[0]==r-mid)
tree[p].nex[0]+=tree[p<<1].nex[0];
tree[p].nex[1]=tree[p<<1|1].nex[1];
if(tree[p<<1|1].nex[1]==r-mid)
tree[p].nex[1]+=tree[p<<1].nex[1];
}
void pushdown(int p,int l,int r){
int mid=(l+r)>>1;
int op=lz[p];
if(op==1){
tree[p<<1].cnt[1]=tree[p<<1].maxx[1]=tree[p<<1].nex[1]=tree[p<<1].pre[1]=0;
tree[p<<1].cnt[0]=tree[p<<1].maxx[0]=tree[p<<1].nex[0]=tree[p<<1].pre[0]=mid-l+1;
tree[p<<1|1].cnt[1]=tree[p<<1|1].maxx[1]=tree[p<<1|1].nex[1]=tree[p<<1|1].pre[1]=0;
tree[p<<1|1].cnt[0]=tree[p<<1|1].maxx[0]=tree[p<<1|1].nex[0]=tree[p<<1|1].pre[0]=r-mid;
lz[p<<1]=lz[p<<1|1]=op;
}
else if(op==2){
tree[p<<1].cnt[1]=tree[p<<1].maxx[1]=tree[p<<1].nex[1]=tree[p<<1].pre[1]=mid-l+1;
tree[p<<1].cnt[0]=tree[p<<1].maxx[0]=tree[p<<1].nex[0]=tree[p<<1].pre[0]=0;
tree[p<<1|1].cnt[1]=tree[p<<1|1].maxx[1]=tree[p<<1|1].nex[1]=tree[p<<1|1].pre[1]=r-mid;
tree[p<<1|1].cnt[0]=tree[p<<1|1].maxx[0]=tree[p<<1|1].nex[0]=tree[p<<1|1].pre[0]=0;
lz[p<<1]=lz[p<<1|1]=op;
}
else{
swap(tree[p<<1].cnt[0],tree[p<<1].cnt[1]);
swap(tree[p<<1].maxx[0],tree[p<<1].maxx[1]);
swap(tree[p<<1].pre[0],tree[p<<1].pre[1]);
swap(tree[p<<1].nex[0],tree[p<<1].nex[1]);
swap(tree[p<<1|1].cnt[0],tree[p<<1|1].cnt[1]);
swap(tree[p<<1|1].maxx[0],tree[p<<1|1].maxx[1]);
swap(tree[p<<1|1].pre[0],tree[p<<1|1].pre[1]);
swap(tree[p<<1|1].nex[0],tree[p<<1|1].nex[1]);
if(lz[p<<1]==0)
lz[p<<1]=op;
else if(lz[p<<1]==1)
lz[p<<1]=2;
else if(lz[p<<1]==2)
lz[p<<1]=1;
else
lz[p<<1]=0;
if(lz[p<<1|1]==0)
lz[p<<1|1]=op;
else if(lz[p<<1|1]==1)
lz[p<<1|1]=2;
else if(lz[p<<1|1]==2)
lz[p<<1|1]=1;
else
lz[p<<1|1]=0;
}
lz[p]=0;
}
void build(int p,int l,int r){
tree[p]={0,0,0,0,0,0};
lz[p]=0;
if(l==r){
if(a[l]){
tree[p].cnt[1]=tree[p].maxx[1]=tree[p].pre[1]=tree[p].nex[1]=1;
}
else{
tree[p].cnt[0]=tree[p].maxx[0]=tree[p].pre[0]=tree[p].nex[0]=1;
}
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p,l,r);
}
void modify(int p,int l,int r,int x,int y,int op){
if(x<=l&&y>=r){
if(op==1){
tree[p].cnt[1]=tree[p].maxx[1]=tree[p].pre[1]=tree[p].nex[1]=0;
tree[p].cnt[0]=tree[p].maxx[0]=tree[p].pre[0]=tree[p].nex[0]=r-l+1;
lz[p]=op;
}
else if(op==2){
tree[p].cnt[1]=tree[p].maxx[1]=tree[p].pre[1]=tree[p].nex[1]=r-l+1;
tree[p].cnt[0]=tree[p].maxx[0]=tree[p].pre[0]=tree[p].nex[0]=0;
lz[p]=op;
}
else{
swap(tree[p].cnt[0],tree[p].cnt[1]);
swap(tree[p].maxx[0],tree[p].maxx[1]);
swap(tree[p].pre[0],tree[p].pre[1]);
swap(tree[p].nex[0],tree[p].nex[1]);
if(lz[p]==0)
lz[p]=op;
else if(lz[p]==1)
lz[p]=2;
else if(lz[p]==2)
lz[p]=1;
else
lz[p]=0;
}
return;
}
if(lz[p])
pushdown(p,l,r);
int mid=(l+r)>>1;
if(x<=mid) modify(p<<1,l,mid,x,y,op);
if(y>mid) modify(p<<1|1,mid+1,r,x,y,op);
pushup(p,l,r);
}
int querycnt(int p,int l,int r,int x,int y){
if(l>=x&&y>=r){
return tree[p].cnt[1];
}
if(lz[p])
pushdown(p,l,r);
int mid=(l+r)>>1;
int res=0;
if(x<=mid) res+=querycnt(p<<1,l,mid,x,y);
if(y>mid) res+=querycnt(p<<1|1,mid+1,r,x,y);
pushup(p,l,r);
return res;
}
int querymax(int p,int l,int r,int x,int y){
if(l>=x&&y>=r){
return tree[p].maxx[1];
}
if(lz[p])
pushdown(p,l,r);
int mid=(l+r)>>1;
int res=0;
if(y<=mid) res=max(res,querymax(p<<1,l,mid,x,y));
else if(x>mid) res=max(res,querymax(p<<1|1,mid+1,r,x,y));
else{
int res1=querymax(p<<1,l,mid,x,y);
int res2=querymax(p<<1|1,mid+1,r,x,y);
res=max(res1,res2);
res=max(res,min(mid-x+1,tree[p<<1].nex[1])+min(y-mid,tree[p<<1|1].pre[1]));
}
pushup(p,l,r);
return res;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
while(m--){
int op,a,b;
cin>>op>>a>>b;
a++,b++;
op++;
if(op==1||op==2||op==3){
modify(1,1,n,a,b,op);
}
else if(op==4){
cout<<querycnt(1,1,n,a,b)<<endl;
}
else{
cout<<querymax(1,1,n,a,b)<<endl;
}
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
}