FiresonZ @ 2022-07-03 19:13:20
QWQ球球了
#include<iostream>
#include<array>
#include<algorithm>
#include<bitset>
#include<cmath>
using namespace std;
using gg=long long;
struct node{
gg maxl,maxr,mmax,l,r,sum;
}zero;
array<gg,400010> tag,chr;
array<array<gg,400010>,2> num,maxl,maxr,mmax;
array<gg,100010> list;
void pushdown(const gg &p,const gg &l,const gg &r)
{
gg mid=(l+r)/2;
if(tag[p]!=2)
{
num[tag[p]^1][p*2]=num[tag[p]^1][p*2+1]=0;
maxl[tag[p]^1][p*2]=maxl[tag[p]^1][p*2+1]=maxr[tag[p]^1][p*2]=maxr[tag[p]^1][p*2+1]=0;
mmax[tag[p]^1][p*2]=mmax[tag[p]^1][p*2+1]=0;
mmax[tag[p]][p*2]=maxr[tag[p]][p*2]=maxl[tag[p]][p*2]=mid-l+1;
mmax[tag[p]][p*2]=maxr[tag[p]][p*2+1]=maxl[tag[p]][p*2+1]=r-mid;
num[tag[p]][p*2]=mid-l+1;
num[tag[p]][p*2+1]=r-mid;
tag[p*2]=tag[p*2+1]=tag[p];
chr[p*2]=chr[p*2+1]=false;
tag[p]=2;
}
if(chr[p])
{
swap(num[0][p*2],num[1][p*2]);
swap(num[0][p*2+1],num[1][p*2+1]);
swap(maxl[0][p*2],maxl[1][p*2]),swap(maxl[0][p*2+1],maxl[1][p*2+1]);
swap(maxr[0][p*2],maxr[1][p*2]),swap(maxr[0][p*2+1],maxr[1][p*2+1]);
swap(mmax[0][p*2],mmax[1][p*2]),swap(mmax[0][p*2+1],mmax[1][p*2+1]);
if(tag[p*2]!=2) tag[p*2]^=1;
else chr[p*2]^=1;
if(tag[p*2+1]!=2) tag[p*2+1]^=1;
else chr[p*2+1]^=1;
chr[p]=false;
}
return;
}
void pushup(const gg &p,const gg &l,const gg &r)
{
gg mid=(l+r)/2;
for(gg i=0;i<2;i++)
{
if(num[i][p*2]==mid-l+1) maxl[i][p]=mid-l+1+maxl[i][p*2+1];
else maxl[i][p]=maxl[i][p*2];
if(num[i][p*2+1]==r-mid) maxr[i][p]=r-mid+maxr[i][p*2];
else maxr[i][p]=maxr[i][p*2+1];
mmax[i][p]=max({maxl[i][p],maxr[i][p],maxr[i][p*2]+maxl[i][p*2+1]});
}
num[0][p]=num[0][p*2]+num[0][p*2+1];
num[1][p]=num[1][p*2]+num[1][p*2+1];
return;
}
void build(const gg &l,const gg &r,const gg &p)
{
tag[p]=2;
if(l==r)
{
mmax[list[l]][p]=maxl[list[l]][p]=maxr[list[l]][p]=1;
num[list[l]][p]++;
return;
}
gg mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
pushup(p,l,r);
return;
}
void update(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p,const gg &k)
{
pushdown(p,nl,nr);
if(nl>=l&&nr<=r)
{
maxl[k^1][p]=maxr[k^1][p]=mmax[k^1][p]=num[k^1][p]=0;
maxl[k][p]=maxr[k][p]=mmax[k][p]=num[k][p]=nr-nl+1;
tag[p]=k;
chr[p]=false;
return;
}
gg mid=(nl+nr)/2;
if(mid>=l)
{
update(l,r,nl,mid,p*2,k);
}
if(mid+1<=r)
{
update(l,r,mid+1,nr,p*2+1,k);
}
pushup(p,nl,nr);
return;
}
void turn(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p)
{
if(nl>=l&&nr<=r)
{
swap(num[1][p],num[0][p]);
swap(maxl[0][p],maxl[1][p]),swap(maxr[0][p],maxr[1][p]),swap(mmax[0][p],mmax[1][p]);
if(tag[p]!=2) tag[p]^=1;
else chr[p]^=1;
return;
}
gg mid=(nl+nr)/2;
pushdown(p,nl,nr);
if(mid>=l)
{
turn(l,r,nl,mid,p*2);
}
if(mid+1<=r)
{
turn(l,r,mid+1,nr,p*2+1);
}
pushup(p,nl,nr);
return;
}
gg getone(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p)
{
if(nl>=l&&nr<=r)
{
return num[1][p];
}
gg mid=(nl+nr)/2,onetp=0;
pushdown(p,nl,nr);
if(mid>=l)
{
onetp=getone(l,r,nl,mid,p*2);
}
if(mid+1<=r)
{
onetp+=getone(l,r,mid+1,nr,p*2+1);
}
pushup(p,nl,nr);
return onetp;
}
node getmax(const gg &l,const gg &r,const gg &nl,const gg &nr,const gg &p)
{
if(nl>=l&&nr<=r)
{
return {maxl[1][p],maxr[1][p],mmax[1][p],nl,nr,num[1][p]};
}
gg mid=(nl+nr)/2;
pushdown(p,nl,nr);
node re=zero;
if(mid<l) return getmax(l,r,mid+1,nr,p*2+1);
if(mid>=r) return getmax(l,r,nl,mid,p*2);
node lson=getmax(l,r,nl,mid,p*2),rson=getmax(l,r,mid+1,nr,p*2+1);
if(lson.sum==lson.r-lson.l+1) re.maxl=lson.r-lson.l+1+rson.maxl;
else re.maxl=lson.maxl;
if(rson.sum==rson.r-rson.l+1) re.maxr=rson.r-rson.l+1+lson.maxr;
else re.maxr=rson.maxr;
re.mmax=max({re.maxl,re.maxr,lson.maxr+rson.maxl});
re.l=lson.l,re.r=rson.r,re.sum=lson.sum+rson.sum;
pushup(p,nl,nr);
return re;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
gg n,m,opt,l,r;
cin>>n>>m;
for(gg i=1;i<=n;i++)
{
cin>>list[i];
}
build(1,n,1);
while(m--)
{
cin>>opt>>l>>r;
l++,r++;
if(opt==0)
{
update(l,r,1,n,1,0);
}
else if(opt==1)
{
update(l,r,1,n,1,1);
}
else if(opt==2)
{
turn(l,r,1,n,1);
}
else if(opt==3)
{
cout<<getone(l,r,1,n,1)<<'\n';
}
else
{
cout<<getmax(l,r,1,n,1).mmax<<'\n';
}
}
return 0;
}
by FiresonZ @ 2022-07-04 11:42:44
捞一下