调了很久的代码。。注意区间翻转和覆盖的操作互相的影响
/* 区间替换操作怎么搞？ 应该是加个tag标记 如果整个区间都是0|1，那么把若有tag的话直接set1|0即可，也不用设置tag标记 反之要设置tag标记，设置了tag标记的区间mx0和mx1要对换 lazy标记可以覆盖tag mx0,mx1表示区间0,1最大连续，lmx0,lmx1表示区间左连续，rmx0，rmx1表示区间右连续 */ #include<bits/stdc++.h> using namespace std; #define maxn 200005 int t,n,m,a[maxn]; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int mx0[maxn<<2],mx1[maxn<<2],lmx0[maxn<<2],rmx0[maxn<<2],lmx1[maxn<<2],rmx1[maxn<<2]; int sum[maxn<<2],lazy[maxn<<2],tag[maxn<<2]; void set0(int l,int r,int rt){tag[rt]=0;lazy[rt]=0;mx0[rt]=lmx0[rt]=rmx0[rt]=r-l+1;sum[rt]=mx1[rt]=lmx1[rt]=rmx1[rt]=0;} void set1(int l,int r,int rt){tag[rt]=0;lazy[rt]=1;mx0[rt]=lmx0[rt]=rmx0[rt]=0;sum[rt]=mx1[rt]=lmx1[rt]=rmx1[rt]=r-l+1;} void rev(int l,int r,int rt){ if(lazy[rt]==0)set1(l,r,rt); else if(lazy[rt]==1)set0(l,r,rt); else { tag[rt]^=1; sum[rt]=r-l+1-sum[rt]; swap(mx0[rt],mx1[rt]); swap(lmx0[rt],lmx1[rt]); swap(rmx0[rt],rmx1[rt]); } } void pushup(int l,int r,int rt){ int m=l+r>>1; lmx0[rt]=lmx0[rt<<1],rmx0[rt]=rmx0[rt<<1|1]; mx0[rt]=max(mx0[rt<<1],mx0[rt<<1|1]); if(rmx0[rt<<1]==m-l+1)lmx0[rt]=lmx0[rt<<1|1]+m-l+1; if(lmx0[rt<<1|1]==r-m)rmx0[rt]=rmx0[rt<<1]+r-m; mx0[rt]=max(mx0[rt],max(lmx0[rt],rmx0[rt])); mx0[rt]=max(mx0[rt],rmx0[rt<<1]+lmx0[rt<<1|1]); lmx1[rt]=lmx1[rt<<1],rmx1[rt]=rmx1[rt<<1|1]; mx1[rt]=max(mx1[rt<<1],mx1[rt<<1|1]); if(rmx1[rt<<1]==m-l+1)lmx1[rt]=lmx1[rt<<1|1]+m-l+1; if(lmx1[rt<<1|1]==r-m)rmx1[rt]=rmx1[rt<<1]+r-m; mx1[rt]=max(mx1[rt],max(lmx1[rt],rmx1[rt])); mx1[rt]=max(mx1[rt],rmx1[rt<<1]+lmx1[rt<<1|1]); sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void pushdown(int l,int r,int rt){ int m=l+r>>1; if(lazy[rt]==0){set0(lson);set0(rson);lazy[rt]=-1;return;} else if(lazy[rt]==1){set1(lson),set1(rson);lazy[rt]=-1;return;} else if(tag[rt]){rev(lson);rev(rson);tag[rt]=0;return;} } void build(int l,int r,int rt){ lazy[rt]=-1; tag[rt]=sum[rt]=0; if(l==r){ if(a[l]==0){mx0[rt]=lmx0[rt]=rmx0[rt]=1;mx1[rt]=lmx1[rt]=rmx1[rt]=0;} else{mx0[rt]=lmx0[rt]=rmx0[rt]=0;mx1[rt]=lmx1[rt]=rmx1[rt]=sum[rt]=1;} return; } int m=l+r>>1; build(lson);build(rson); pushup(l,r,rt); } void update0(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){set0(l,r,rt);return;} int m=l+r>>1; pushdown(l,r,rt); if(L<=m)update0(L,R,lson); if(R>m)update0(L,R,rson); pushup(l,r,rt); } void update1(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){set1(l,r,rt);return;} int m=l+r>>1; pushdown(l,r,rt); if(L<=m)update1(L,R,lson); if(R>m)update1(L,R,rson); pushup(l,r,rt); } void update2(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){rev(l,r,rt);return;} int m=l+r>>1; pushdown(l,r,rt); if(L<=m)update2(L,R,lson); if(R>m)update2(L,R,rson); pushup(l,r,rt); } int query1(int L,int R,int l,int r,int rt){ if(L<=l &&R>=r){return sum[rt];} int m=l+r>>1,res=0; pushdown(l,r,rt); if(L<=m)res+=query1(L,R,lson); if(R>m)res+=query1(L,R,rson); pushup(l,r,rt); return res; } int query2(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){return mx1[rt];} int m=l+r>>1; pushdown(l,r,rt); if(R<=m)return query2(L,R,lson); else if(L>m)return query2(L,R,rson); else { int t1=query2(L,R,lson),t2=query2(L,R,rson); int t3=max(t1,t2); return max(t3,min(rmx1[rt<<1],m-L+1)+min(lmx1[rt<<1|1],R-m)); } pushup(l,r,rt); } int main(){ cin>>t; while(t--){ cin>>n>>m; for(int i=0;i<n;i++)cin>>a[i]; build(0,n-1,1); while(m--){ int opt,l,r; cin>>opt>>l>>r; //l++,r++; if(opt==0)update0(l,r,0,n-1,1); if(opt==1)update1(l,r,0,n-1,1); if(opt==2)update2(l,r,0,n-1,1); if(opt==3)cout<<query1(l,r,0,n-1,1)<<' '; if(opt==4)cout<<query2(l,r,0,n-1,1)<<' '; } } }