dubnium @ 2024-07-15 13:50:18
提交记录:https://www.luogu.com.cn/record/166105173
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+6;
struct Segment_tree {
int l,r,sum,lmax[2],rmax[2],dat[2],tag[2];//0覆盖,1翻转
} T[maxn<<2];
int n,m;
int c[maxn];
int len(int p) {
return T[p].r-T[p].l+1;
}
bool check(int p,bool t) {
return T[p].sum==t*len(p);
}
void pushup(int p) {
T[p].sum=T[p<<1].sum+T[p<<1|1].sum;
for(int i=0; i<=1; i++) {
T[p].lmax[i]=T[p<<1].lmax[i];
if(check(p<<1,i))
T[p].lmax[i]=max(T[p].lmax[i],len(p<<1)+T[p<<1|1].lmax[i]);
T[p].rmax[i]=T[p<<1|1].rmax[i];
if(check(p<<1|1,i))
T[p].rmax[i]=max(T[p].rmax[i],len(p<<1|1)+T[p<<1].rmax[i]);
T[p].dat[i]=max({T[p<<1].dat[i],T[p<<1].rmax[i]+T[p<<1|1].lmax[i],T[p<<1|1].dat[i]});
}
}
void spread(int p) {
if(~T[p].tag[0]) {
int t=T[p].tag[0];
T[p<<1].sum=len(p<<1),T[p<<1|1].sum=len(p<<1|1);
T[p<<1].lmax[t]=T[p<<1].rmax[t]=T[p<<1].dat[t]=len(p<<1);
T[p<<1|1].lmax[t]=T[p<<1|1].rmax[t]=T[p<<1|1].dat[t]=len(p<<1|1);
T[p<<1].lmax[t^1]=T[p<<1].rmax[t^1]=T[p<<1].dat[t^1]=0;
T[p<<1|1].lmax[t^1]=T[p<<1|1].rmax[t^1]=T[p<<1|1].dat[t^1]=0;
T[p<<1].tag[0]=T[p<<1|1].tag[0]=t,T[p<<1].tag[1]=T[p<<1|1].tag[1]=0;
T[p].tag[0]=-1;
//puts("f");
}
if(T[p].tag[1]) {
T[p<<1].sum=len(p<<1)-T[p<<1].sum,T[p<<1|1].sum=len(p<<1|1)-T[p<<1|1].sum;
swap(T[p<<1].lmax[0],T[p<<1].lmax[1]),swap(T[p<<1].rmax[0],T[p<<1].rmax[1]);
swap(T[p<<1].dat[0],T[p<<1].dat[1]);
swap(T[p<<1|1].lmax[0],T[p<<1|1].lmax[1]),swap(T[p<<1|1].rmax[0],T[p<<1|1].rmax[1]);
swap(T[p<<1|1].dat[0],T[p<<1|1].dat[1]);
//printf("b\n%d %d %d %d %d %d %dj\n",p,T[p].l,T[p].r,T[p<<1].tag[0],T[p<<1].tag[1],T[p<<1|1].tag[0],T[p<<1|1].tag[1]);
if(~T[p<<1].tag[0])
T[p<<1].tag[0]^=1;
else T[p<<1].tag[1]^=1;
if(~T[p<<1|1].tag[0])
T[p<<1|1].tag[0]^=1;
else T[p<<1|1].tag[1]^=1;
T[p].tag[1]=0;
//puts("q");
}
}
void Build(int p,int l,int r) {
T[p].l=l,T[p].r=r,T[p].tag[0]=-1,T[p].tag[1]=0;;
if(l==r) {
T[p].sum=c[l],T[p].lmax[c[l]]=T[p].rmax[c[l]]=T[p].dat[c[l]]=1;
return ;
}
int mid=l+r>>1;
Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
pushup(p);
}
void change(int p,int x,int y,int t) { //0/1:覆盖为0/1,2:翻转
if(x<=T[p].l&&T[p].r<=y) {
if(!t) {
T[p].sum=T[p].lmax[1]=T[p].rmax[1]=T[p].dat[1]=0,T[p].tag[1]=0;
T[p].lmax[0]=T[p].rmax[0]=T[p].dat[0]=len(p),T[p].tag[0]=0;
} else if(t==1) {
T[p].sum=T[p].lmax[1]=T[p].rmax[1]=T[p].dat[1]=len(p),T[p].tag[1]=0;
T[p].lmax[0]=T[p].rmax[0]=T[p].dat[0]=0,T[p].tag[0]=1;
} else {
T[p].sum=len(p)-T[p].sum;
if(~T[p].tag[0])
T[p].tag[0]^=1;
else T[p].tag[1]^=1;
swap(T[p].lmax[0],T[p].lmax[1]),swap(T[p].rmax[0],T[p].rmax[1]),swap(T[p].dat[0],T[p].dat[1]);
//printf("%d %d %d %d %d %dp\n",p,T[p].l,T[p].r,t,T[p].dat[0],T[p].dat[1]);
}
return ;
}
spread(p);
int mid=T[p].l+T[p].r>>1;
if(x<=mid)
change(p<<1,x,y,t);
if(y>mid)
change(p<<1|1,x,y,t);
pushup(p);
}
int ask(int p,int x,int y) {
if(x<=T[p].l&&T[p].r<=y)
return T[p].sum;
spread(p);
int mid=T[p].l+T[p].r>>1,res=0;
if(x<=mid)
res+=ask(p<<1,x,y);
if(y>mid)
res+=ask(p<<1|1,x,y);
return res;
}
Segment_tree query(int p,int x,int y) {
if(x<=T[p].l&&T[p].r<=y) {
//printf("%dx %dy %d %d %d %d %dv\n",x,y,p,T[p].l,T[p].r,T[p].dat[0],T[p].dat[1]);
return T[p];
}
spread(p);
int mid=T[p].l+T[p].r>>1;
if(x>mid)
return query(p<<1|1,x,y);
if(y<=mid)
return query(p<<1,x,y);
Segment_tree a,b,res;
a=query(p<<1,x,y),b=query(p<<1|1,x,y);
res.sum=a.sum+b.sum;
res.lmax[1]=a.lmax[1];
if(a.sum==a.r-a.l+1)
res.lmax[1]=max(res.lmax[1],len(p<<1)+b.lmax[1]);
res.rmax[1]=b.rmax[1];
if(b.sum==b.r-b.l+1)
res.rmax[1]=max(res.rmax[1],len(p<<1|1)+a.rmax[1]);
res.dat[1]=max({a.dat[1],a.rmax[1]+b.lmax[1],b.dat[1]});
//printf("%d %d %dr\n",T[p].l,T[p].r,res.dat[1]);
return res;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",&c[i]);
Build(1,1,n);
int op,l,r;
while(m--) {
//for(int i=1; i<=n; i++)
// printf("%d ",query(1,i,i).dat[1]);
//puts("g");
scanf("%d%d%d",&op,&l,&r),l++,r++;
if(op<=2)
change(1,l,r,op);
else if(op==3)
printf("%d\n",ask(1,l,r));
else printf("%d\n",query(1,l,r).dat[1]);
}
return 0;
}