NOI2017的简化版……
就是维护的时候要想清楚怎么讨论。
#include<bits/stdc++.h> #define lson (o<<1) #define rson (o<<1|1) const int N=100010; using namespace std; int n,m; int a[N]; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } struct Segment_Tree{ int sumv[N<<2],rev[N<<2],setv[N<<2],maxl[N<<2][2],maxr[N<<2][2],maxv[N<<2][2]; inline void pushup(int o,int l,int r){ int mid=(l+r)>>1; maxl[o][0]=maxl[lson][0]; if(maxl[lson][0]==mid-l+1)maxl[o][0]+=maxl[rson][0]; maxr[o][1]=maxr[rson][1]; if(maxr[rson][1]==r-mid)maxr[o][1]+=maxr[lson][1]; maxl[o][1]=maxl[lson][1]; if(maxl[lson][1]==mid-l+1)maxl[o][1]+=maxl[rson][1]; maxr[o][0]=maxr[rson][0]; if(maxr[rson][0]==r-mid)maxr[o][0]+=maxr[lson][0]; maxv[o][1]=max(maxv[lson][1],max(maxv[rson][1],maxr[lson][1]+maxl[rson][1])); maxv[o][0]=max(maxv[lson][0],max(maxv[rson][0],maxr[lson][0]+maxl[rson][0])); sumv[o]=sumv[lson]+sumv[rson]; } inline void pushdown(int o,int l,int r){ int mid=(l+r)>>1; if(setv[o]!=-1){ int tag=setv[o];setv[lson]=setv[rson]=setv[o]; sumv[lson]=tag*(mid-l+1);sumv[rson]=tag*(r-mid); maxv[lson][tag]=maxl[lson][tag]=maxr[lson][tag]=mid-l+1; maxv[rson][tag]=maxl[rson][tag]=maxr[rson][tag]=r-mid; maxv[lson][tag^1]=maxl[lson][tag^1]=maxr[lson][tag^1]=0; maxv[rson][tag^1]=maxl[rson][tag^1]=maxr[rson][tag^1]=0; setv[o]=-1;rev[o]=0; } if(rev[o]){ int lx=0,rx=lx^1; rev[lson]^=1;rev[rson]^=1; swap(maxv[lson][lx],maxv[lson][rx]);swap(maxv[rson][lx],maxv[rson][rx]); swap(maxl[lson][lx],maxl[lson][rx]);swap(maxl[rson][lx],maxl[rson][rx]); swap(maxr[lson][lx],maxr[lson][rx]);swap(maxr[rson][lx],maxr[rson][rx]); sumv[lson]=mid-l+1-sumv[lson];sumv[rson]=r-mid-sumv[rson]; if(setv[lson]!=-1)setv[lson]^=1; if(setv[rson]!=-1)setv[rson]^=1; rev[o]=0; } } inline void build(int o,int l,int r){ rev[o]=0;setv[o]=-1; if(l==r){ sumv[o]=a[l];int lx=a[l],rx=lx^1; maxv[o][lx]=maxl[o][lx]=maxr[o][lx]=1; maxv[o][rx]=maxl[o][rx]=maxr[o][rx]=0; return; } int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(o,l,r); } inline void sett(int o,int l,int r,int ql,int qr,int v){ if(ql<=l&&r<=qr){int rx=v^1; sumv[o]=(r-l+1)*v;setv[o]=v;maxv[o][v]=maxl[o][v]=maxr[o][v]=r-l+1; rev[o]=0;maxv[o][rx]=maxl[o][rx]=maxr[o][rx]=0; return; } int mid=(l+r)>>1;pushdown(o,l,r); if(ql<=mid)sett(lson,l,mid,ql,qr,v); if(qr>mid)sett(rson,mid+1,r,ql,qr,v); pushup(o,l,r); } inline void rever(int o,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ rev[o]^=1;swap(maxv[o][0],maxv[o][1]);swap(maxl[o][0],maxl[o][1]);swap(maxr[o][0],maxr[o][1]); sumv[o]=(r-l+1)-sumv[o]; if(setv[o]!=-1)setv[o]^=1; return; } int mid=(l+r)>>1;pushdown(o,l,r); if(ql<=mid)rever(lson,l,mid,ql,qr); if(qr>mid)rever(rson,mid+1,r,ql,qr); pushup(o,l,r); } inline int querysum(int o,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr)return sumv[o]; int mid=(l+r)>>1,ans=0; pushdown(o,l,r); if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr); if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr); return ans; } inline int querymax(int o,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr)return maxv[o][1]; int mid=(l+r)>>1;int ans=0; pushdown(o,l,r); if(ql<=mid)ans=max(ans,querymax(lson,l,mid,ql,qr)); if(qr>mid)ans=max(ans,querymax(rson,mid+1,r,ql,qr)); if(ql<=mid&&qr>mid)ans=max(ans,min(mid-ql+1,maxr[lson][1])+min(qr-mid,maxl[rson][1])); return ans; } }T; int main(){ n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); T.build(1,1,n); while(m--){ int opt=read(),l=read(),r=read(); l++;r++; if(opt==0)T.sett(1,1,n,l,r,0); if(opt==1)T.sett(1,1,n,l,r,1); if(opt==2)T.rever(1,1,n,l,r); if(opt==3)printf("%d ",T.querysum(1,1,n,l,r)); if(opt==4)printf("%d ",T.querymax(1,1,n,l,r)); } }