bktchizhi_fzh @ 2022-11-22 19:37:03
感觉讨论区提醒的也注意了呀
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 100010
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
int a[N],n,m,op,l,r;
struct Tree{
int qufan,fugai;
int sum;
int lmax1,rmax1,maxn1;
int lmax0,rmax0,maxn0;
Tree(){
fugai=-1;
}
}tr[4*N];
void push_up(int p,int l,int r){
int mid=(l+r)>>1;
tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
tr[p].lmax1=tr[ls(p)].lmax1==mid-l+1?tr[ls(p)].lmax1+tr[rs(p)].lmax1:tr[ls(p)].lmax1;
tr[p].rmax1=tr[rs(p)].rmax1==r-mid?tr[rs(p)].rmax1+tr[ls(p)].rmax1:tr[rs(p)].rmax1;
tr[p].maxn1=max(max(tr[ls(p)].maxn1,tr[rs(p)].maxn1),tr[ls(p)].rmax1+tr[rs(p)].lmax1);
tr[p].lmax0=tr[ls(p)].lmax0==mid-l+1?tr[ls(p)].lmax0+tr[rs(p)].lmax0:tr[ls(p)].lmax0;
tr[p].rmax0=tr[rs(p)].rmax0==r-mid?tr[rs(p)].rmax0+tr[ls(p)].rmax0:tr[rs(p)].rmax0;
tr[p].maxn0=max(max(tr[ls(p)].maxn0,tr[rs(p)].maxn0),tr[ls(p)].rmax0+tr[rs(p)].lmax0);
}
void push_down(int p,int l,int r){
int mid=(l+r)>>1;
if(tr[p].fugai!=-1){
if(tr[p].fugai==1){
tr[ls(p)].fugai=1;
tr[rs(p)].fugai=1;
tr[ls(p)].qufan=0;
tr[rs(p)].qufan=0;
tr[ls(p)].sum=mid-l+1;
tr[rs(p)].sum=r-mid;
tr[ls(p)].lmax1=tr[ls(p)].rmax1=tr[ls(p)].maxn1=mid-l+1;
tr[ls(p)].lmax0=tr[ls(p)].rmax0=tr[ls(p)].maxn0=0;
tr[rs(p)].lmax1=tr[rs(p)].rmax1=tr[rs(p)].maxn1=r-mid;
tr[rs(p)].lmax0=tr[rs(p)].rmax0=tr[rs(p)].maxn0=0;
} else {
tr[ls(p)].fugai=0;
tr[rs(p)].fugai=0;
tr[ls(p)].qufan=0;
tr[rs(p)].qufan=0;
tr[ls(p)].sum=0;
tr[rs(p)].sum=0;
tr[ls(p)].lmax1=tr[ls(p)].rmax1=tr[ls(p)].maxn1=0;
tr[ls(p)].lmax0=tr[ls(p)].rmax0=tr[ls(p)].maxn0=mid-l+1;
tr[rs(p)].lmax1=tr[rs(p)].rmax1=tr[rs(p)].maxn1=0;
tr[rs(p)].lmax0=tr[rs(p)].rmax0=tr[rs(p)].maxn0=r-mid;
}
tr[p].fugai=-1;
}
if(tr[p].qufan){
tr[ls(p)].qufan=tr[p].qufan;
int l0=tr[ls(p)].lmax0,r0=tr[ls(p)].rmax0,m0=tr[ls(p)].maxn0;
int l1=tr[ls(p)].lmax1,r1=tr[ls(p)].rmax1,m1=tr[ls(p)].maxn1;
int sum1=tr[ls(p)].sum;
tr[ls(p)].sum=mid-l+1-sum1;
tr[ls(p)].maxn1=m0,tr[ls(p)].lmax1=l0,tr[ls(p)].rmax1=r0;
tr[ls(p)].maxn0=m1,tr[ls(p)].lmax0=l1,tr[ls(p)].rmax0=r1;
tr[rs(p)].qufan=tr[p].qufan;
l0=tr[rs(p)].lmax0,r0=tr[rs(p)].rmax0,m0=tr[rs(p)].maxn0;
l1=tr[rs(p)].lmax1,r1=tr[rs(p)].rmax1,m1=tr[rs(p)].maxn1;
sum1=tr[rs(p)].sum;
tr[rs(p)].sum=r-mid-sum1;
tr[rs(p)].maxn1=m0,tr[rs(p)].lmax1=l0,tr[rs(p)].rmax1=r0;
tr[rs(p)].maxn0=m1,tr[rs(p)].lmax0=l1,tr[rs(p)].rmax0=r1;
tr[p].qufan^=1;
}
}
void build(int p,int l,int r){
if(l==r){
tr[p].fugai=-1;
tr[p].qufan=0;
tr[p].lmax1=tr[p].rmax1=tr[p].maxn1=tr[p].sum=a[l];
tr[p].lmax0=tr[p].rmax0=tr[p].maxn0=a[l]^1;
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p,l,r);
}
void Cover0(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
tr[p].fugai=0;
tr[p].qufan=0;
tr[p].sum=0;
tr[p].lmax0=tr[p].rmax0=tr[p].maxn0=r-l+1;
tr[p].lmax1=tr[p].rmax1=tr[p].maxn1=0;
return;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)Cover0(ls(p),l,mid,x,y);
if(mid<y)Cover0(rs(p),mid+1,r,x,y);
push_up(p,l,r);
}
void Cover1(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
tr[p].fugai=1;
tr[p].qufan=0;
tr[p].sum=r-l+1;
tr[p].lmax0=tr[p].rmax0=tr[p].maxn0=0;
tr[p].lmax1=tr[p].rmax1=tr[p].maxn1=r-l+1;
return;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)Cover1(ls(p),l,mid,x,y);
if(mid<y)Cover1(rs(p),mid+1,r,x,y);
push_up(p,l,r);
}
void update(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
tr[p].qufan^=1;
int m0=tr[p].maxn0,l0=tr[p].lmax0,r0=tr[p].rmax0;
int m1=tr[p].maxn1,l1=tr[p].lmax1,r1=tr[p].rmax1;
int sum1=tr[p].sum;
tr[p].sum=r-l+1-sum1;
tr[p].maxn1=m0,tr[p].lmax1=l0,tr[p].rmax1=r0;
tr[p].maxn0=m1,tr[p].lmax0=l1,tr[p].rmax0=r1;
return;
}
int mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)update(ls(p),l,mid,x,y);
if(mid<y)update(rs(p),mid+1,r,x,y);
push_up(p,l,r);
}
int Sum(int p,int l,int r,int x,int y){
if(x<=l&&r<=y)return tr[p].sum;
int res=0,mid=(l+r)>>1;
push_down(p,l,r);
if(mid>=x)res+=Sum(ls(p),l,mid,x,y);
if(mid<y)res+=Sum(rs(p),mid+1,r,x,y);
return res;
}
int Ctn1(int p,int l,int r,int x,int y){
if(x<=l&&r<=y)return tr[p].maxn1;
int mid=(l+r)>>1,resl=0,resr=0,res=0;
push_down(p,l,r);
if(mid>=x){
resl=Ctn1(ls(p),l,mid,x,y);
if(tr[ls(p)].rmax1>mid-x+1)res+=mid-x+1;
else res+=tr[ls(p)].lmax1;
}
if(mid<y){
resr=Ctn1(rs(p),mid+1,r,x,y);
if(tr[rs(p)].lmax1>y-mid)res+=y-mid;
else res+=tr[rs(p)].lmax1;
}
return max(max(resl,resr),res);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build(1,1,n);
while(m--){
scanf("%d%d%d",&op,&l,&r);
l++;r++;
if(op==0)Cover0(1,1,n,l,r);
if(op==1)Cover1(1,1,n,l,r);
if(op==2)update(1,1,n,l,r);
if(op==3)printf("%d\n",Sum(1,1,n,l,r));
if(op==4)printf("%d\n",Ctn1(1,1,n,l,r));
}
return 0;
}
by bktchizhi_fzh @ 2022-11-23 20:09:26
过了,此贴完结