#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <cassert> using namespace std; const int maxn=100000+5; #define lson (o<<1) #define rson (o<<1|1) int a[maxn],n,m; namespace segment_tree{ int sumv[maxn*6],setv[maxn*6],lefc[2][maxn*6],rghc[2][maxn*6],cot[2][maxn*6]; bool rev[maxn*6]; void () { memset(setv,-1,sizeof(setv)); } void maintain(int o, int l,int r) { sumv[o]=sumv[lson]+sumv[rson]; int mid=(l+r)>>1; cot[0][o]=max(max(cot[0][lson],cot[0][rson]),rghc[0][lson]+lefc[0][rson]); cot[1][o]=max(max(cot[1][lson],cot[1][rson]),rghc[1][lson]+lefc[1][rson]); lefc[0][o]=lefc[0][lson]; if(sumv[lson]==0) lefc[0][o]=mid-l+1+lefc[0][rson]; lefc[1][o]=lefc[1][lson]; if(sumv[lson]==(mid-l+1)) lefc[1][o]=mid-l+1+lefc[1][rson]; rghc[0][o]=rghc[0][rson]; if(sumv[rson]==0) rghc[0][o]=r-mid+rghc[0][lson]; rghc[1][o]=rghc[1][rson]; if(sumv[rson]==(r-mid)) rghc[1][o]=r-mid+rghc[1][lson]; if(setv[o]!=-1){ sumv[o]=setv[o]*(r-l+1); cot[0][o]=lefc[0][o]=rghc[0][o]=(setv[o]==0)*(r-l+1); cot[1][o]=lefc[1][o]=rghc[1][o]=(setv[o]==1)*(r-l+1); } if(rev[o]){ sumv[o]=(r-l+1)-sumv[o]; swap(cot[0][o],cot[1][o]),swap(lefc[0][o],lefc[1][o]),swap(rghc[0][o],rghc[1][o]); } } void getrev(int o,int l,int r) { rev[o]^=1; maintain(o,l,r); } void getset(int o,int l,int r,int val) { rev[o]=0; setv[o]=val; maintain(o,l,r); } void pushdown(int o,int l,int r) { int mid=(l+r)>>1; if(setv[o]!=-1){ getset(lson,l,mid,setv[o]); getset(rson,mid+1,r,setv[o]); setv[o]=-1; maintain(o,l,r); } if(rev[o]){ getrev(lson,l,mid);getrev(rson,mid+1,r); rev[o]=0; maintain(o,l,r); } } void Set(int o,int l,int r,int ql,int qr,int val) { if(ql>r || qr<l) return; if(ql<=l && r<=qr) {getset(o,l,r,val);return;} else{ int mid=(l+r)>>1; pushdown(o,l,r); if(ql<=mid) Set(lson,l,mid,ql,qr,val); if(qr>mid) Set(rson,mid+1,r,ql,qr,val); maintain(o,l,r); } } void Rev(int o,int l,int r,int ql,int qr) { if(ql>r || qr<l) return; if(ql<=l && r<=qr) {getrev(o,l,r);return;} else{ int mid=(l+r)>>1; pushdown(o,l,r); if(ql<=mid) Rev(lson,l,mid,ql,qr); if(qr>mid) Rev(rson,mid+1,r,ql,qr); maintain(o,l,r); } } int Qsum(int o,int l,int r,int ql,int qr) { if(ql>r || qr<l) return 0; if(ql<=l && r<=qr) return sumv[o]; else{ int mid=(l+r)>>1; pushdown(o,l,r); int ret=0; if(ql<=mid) ret+=Qsum(lson,l,mid,ql,qr); if(qr>mid) ret+=Qsum(rson,mid+1,r,ql,qr); return ret; } } int Qcon(int o,int l,int r,int ql,int qr,int dir) { if(ql>r || qr<l) return 0; if(ql<=l && r<=qr){ if(dir==0) return cot[1][o]; if(dir==1) return lefc[1][o]; if(dir==2) return rghc[1][o]; }else{ int mid=(l+r)>>1; pushdown(o,l,r); if(qr<=mid) return Qcon(lson,l,mid,ql,qr,dir); else if(ql>mid) return Qcon(rson,mid+1,r,ql,qr,dir); else{ int mid=(l+r)>>1; if(dir==0){ int ret=0; ret=max(ret,Qcon(lson,l,mid,ql,qr,2)+Qcon(rson,mid+1,r,ql,qr,1)); ret=max(ret,Qcon(lson,l,mid,ql,qr,0)); ret=max(ret,Qcon(rson,mid+1,r,ql,qr,0)); return ret; }else if(dir==1){ int sm=Qsum(lson,l,mid,ql,qr); if(sm==mid-max(l,ql)+1){ return sm+Qcon(rson,mid+1,r,ql,qr,1); }else return Qcon(lson,l,mid,ql,qr,1); }else{ int sm=Qsum(rson,mid+1,r,ql,qr); if(sm==min(r,qr)-mid){ return sm+Qcon(lson,l,mid,ql,qr,2); }else return Qcon(rson,mid+1,r,ql,qr,2); } assert(0); } assert(0); } } }; using namespace segment_tree; int main() { ini(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); Set(1,1,n,i,i,a[i]); } int op,l,r; for(int i=1;i<=m;i++){ scanf("%d%d%d",&op,&l,&r); l++,r++; if(op==0) Set(1,1,n,l,r,0); else if(op==1) Set(1,1,n,l,r,1); else if(op==2) Rev(1,1,n,l,r); else if(op==3) printf("%dn",Qsum(1,1,n,l,r)); else printf("%dn",Qcon(1,1,n,l,r,0)); } return 0; }
|
近期评论