dyyzy @ 2023-08-24 11:35:40
rt，代码放二楼了
by dyyzy @ 2023-08-24 11:35:56
#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
int x=0;char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
const int N=1e5+10;
struct Node{int l,r,sum,tag,l0,r0,l1,r1,max0,max1;}t[N<<2];
//tag = -2（没有tag）；-1（区间反转）；0（区间赋0）；1（区间赋1）
//l0 左端0 r0 右端0 l1 左端1 r1 右端1
Node operator +(const Node &a,const Node &b){
Node res;
res.l=a.l,res.r=b.r,res.sum=a.sum+b.sum,res.tag=-2;
res.l0=(a.sum==0)?(a.r-a.l+1)+b.l0:a.l0;
res.l1=(a.sum==(a.r-a.l+1))?(a.r-a.l+1)+b.l1:a.l1;
res.r0=(b.sum==0)?(b.r-b.l+1)+a.r0:b.r0;
res.r1=(b.sum==(b.r-b.l+1))?(b.r-b.l+1)+a.r1:b.r1;
res.max1=max(max(a.max1,b.max1),(a.r1+b.l1));
res.max0=max(max(a.max0,b.max0),(a.r0+b.l0));
return res;
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){int x=read();t[p].tag=-2,t[p].sum=x;t[p].l0=t[p].r0=t[p].max0=(x^1);t[p].l1=t[p].r1=t[p].max1=x;return;}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p]=t[p<<1]+t[p<<1|1];
}
inline void spread(int p){
if(t[p].tag==-1){
swap(t[p<<1].l1,t[p<<1].l0);swap(t[p<<1|1].l1,t[p<<1|1].l0);
swap(t[p<<1].r1,t[p<<1].r0);swap(t[p<<1|1].r1,t[p<<1|1].r0);
swap(t[p<<1].max1,t[p<<1].max0);swap(t[p<<1|1].max1,t[p<<1|1].max0);
t[p<<1].sum=(t[p<<1].r-t[p<<1].l+1)-t[p<<1].sum;t[p<<1|1].sum=(t[p<<1|1].r-t[p<<1|1].l+1)-t[p<<1|1].sum;
if(t[p<<1].tag==0 || t[p<<1].tag==1) t[p<<1].tag^=1;
else if(t[p<<1|1].tag==0 || t[p<<1|1].tag==1) t[p<<1|1].tag^=1;
if(t[p<<1].tag==-1) t[p<<1].tag=-2;else if(t[p<<1].tag==-2) t[p<<1].tag=-1;
if(t[p<<1|1].tag==-1) t[p<<1|1].tag=-2;else if(t[p<<1|1].tag==-2) t[p<<1|1].tag=-1;
t[p].tag=-2;
}else if(t[p].tag!=-2){
t[p<<1].max1=t[p<<1].sum=t[p].tag*(t[p<<1].r-t[p<<1].l+1);t[p<<1].max0=(t[p].tag^1)*(t[p<<1].r-t[p<<1].l+1);
t[p<<1|1].max1=t[p<<1|1].sum=t[p].tag*(t[p<<1|1].r-t[p<<1|1].l+1);t[p<<1|1].max0=(t[p].tag^1)*(t[p<<1|1].r-t[p<<1|1].l+1);
t[p<<1].l1=t[p<<1|1].l1=t[p<<1].r1=t[p<<1|1].r1=t[p].tag;
t[p<<1].l0=t[p<<1|1].l0=t[p<<1].r0=t[p<<1|1].r0=(t[p].tag^1);
t[p<<1].tag=t[p<<1|1].tag=t[p].tag;
t[p].tag=-2;
}
}
void change(int p,int l,int r,int val){
if(l<=t[p].l && t[p].r<=r){t[p].tag=val;t[p].sum=t[p].l1=t[p].r1=t[p].max1=val*(t[p].r-t[p].l+1);t[p].l0=t[p].r0=t[p].max0=(val^1)*(t[p].r-t[p].l+1);return;}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) change(p<<1,l,r,val);
if(mid<r) change(p<<1|1,l,r,val);
t[p]=t[p<<1]+t[p<<1|1];
}
void _swap(int p,int l,int r){
if(l<=t[p].l && t[p].r<=r){
if(t[p].tag==1) t[p].tag=0;else if(t[p].tag==0) t[p].tag=1;else if(t[p].tag==-1) t[p].tag=-2;else t[p].tag=-1;
swap(t[p].l1,t[p].l0);swap(t[p].r1,t[p].r0);swap(t[p].max1,t[p].max0);t[p].sum=(t[p].r-t[p].l+1)-t[p].sum;return;
}
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) _swap(p<<1,l,r);
if(mid<r) _swap(p<<1|1,l,r);
t[p]=t[p<<1]+t[p<<1|1];
}
int query1(int p,int l,int r){
if(l<=t[p].l && t[p].r<=r) return t[p].sum;
spread(p);
int mid=(t[p].l+t[p].r)>>1,res=0;
if(l<=mid) res+=query1(p<<1,l,r);
if(mid<r) res+=query1(p<<1|1,l,r);
return res;
}
Node query2(int p,int l,int r){
if(l<=t[p].l && t[p].r<=r) return t[p];
spread(p);
int mid=(t[p].l+t[p].r)>>1;
if(l>mid) return query2(p<<1|1,l,r);
if(r<=mid) return query2(p<<1,l,r);
Node res=query2(p<<1,l,r)+query2(p<<1|1,l,r);
return res;
}
int main(){
// freopen("114.in","r",stdin);
// freopen("114.out","w",stdout);
int n=read(),m=read();
build(1,1,n);
for(int i=1;i<=m;++i){
int op=read(),l=read()+1,r=read()+1;
if(op==0) change(1,l,r,0);
if(op==1) change(1,l,r,1);
if(op==2) _swap(1,l,r);
if(op==3) cout<<query1(1,l,r)<<'\n';
if(op==4) cout<<query2(1,l,r).max1<<'\n';
}
return 0;
}by dyyzy @ 2023-08-24 11:36:49
@dyyzy_qwq 感觉不需要使用两个tag QwQ
by WrongAnswer_90 @ 2023-08-24 14:02:29
spread 推平写错了
by dyyzy @ 2023-08-24 15:22:08
@WrongAnswer_90 thx，自己还有点问题，现在调过了
by hello_world_djh @ 2023-08-24 20:55:27
orz数据结构代师