_HCl_ @ 2022-02-20 16:40:29
求助神佬告诉我我的代码哪有问题
#include<bits/stdc++.h>
using namespace std;
struct treeNode{
int l,r;
int sum;
int tag,rev;
int max[2],lmax[2],rmax[2];
};
int n,m;
treeNode tr[1000001];
int a[1000001];
void push_up(int p)
{
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
for(int i=0;i<=1;++i)
{
tr[p].lmax[i]=tr[p<<1].lmax[i];
if(i==0)
{
if(tr[p<<1].sum==0)
{
tr[p].lmax[i]+=tr[p<<1|1].lmax[i];
}
}
else
{
if(tr[p<<1].sum==tr[p<<1].r-tr[p<<1].l+1)
{
tr[p].lmax[i]+=tr[p<<1|1].rmax[i];
}
}
tr[p].rmax[i]=tr[p<<1|1].rmax[i];
if(i==0)
{
if(tr[p<<1|1].sum==0)
{
tr[p].rmax[i]+=tr[p<<1].rmax[i];
}
}
else
{
if(tr[p<<1|1].sum==tr[p<<1|1].r-tr[p<<1|1].l+1)
{
tr[p].rmax[i]+=tr[p<<1].rmax[i];
}
}
tr[p].max[i]=max(tr[p<<1].rmax[i]+tr[p<<1|1].lmax[i],max(tr[p<<1].max[i],tr[p<<1|1].max[i]));
}
}
void build(int p,int l,int r)
{
tr[p].l=l;
tr[p].r=r;
tr[p].tag=-1;
if(l==r)
{
tr[p].sum=a[l];
if(a[l]==0)
{
tr[p].max[0]=tr[p].lmax[0]=tr[p].rmax[0]=1;
}
else
{
tr[p].max[1]=tr[p].lmax[1]=tr[p].rmax[1]=1;
}
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
}
void push_down(int p)
{
if(tr[p].tag!=-1)
{
tr[p].rev=0;
int tag=tr[p].tag;
tr[p<<1].sum=tag*(tr[p<<1].r-tr[p<<1].l+1);
tr[p<<1|1].sum=tag*(tr[p<<1|1].r-tr[p<<1|1].l+1);
tr[p<<1].max[tag]=tr[p<<1].lmax[tag]=tr[p<<1].rmax[tag]=tr[p<<1].r-tr[p<<1].l+1;
tr[p<<1].max[tag^1]=tr[p<<1].lmax[tag^1]=tr[p<<1].rmax[tag^1]=0;
tr[p<<1|1].max[tag]=tr[p<<1|1].lmax[tag]=tr[p<<1|1].rmax[tag]=tr[p<<1|1].r-tr[p<<1|1].l+1;
tr[p<<1|1].max[tag^1]=tr[p<<1|1].lmax[tag^1]=tr[p<<1|1].rmax[tag^1]=0;
tr[p<<1].tag=tr[p<<1|1].tag=tag;
tr[p<<1].rev=tr[p<<1|1].rev=0;
tr[p].tag=-1;
}
if(tr[p].rev)
{
tr[p<<1].sum=tr[p<<1].r-tr[p<<1].l+1-tr[p<<1].sum;
tr[p<<1|1].sum=tr[p<<1|1].r-tr[p<<1|1].l+1-tr[p<<1|1].sum;
if(tr[p<<1].tag!=-1)
{
tr[p<<1].tag^=1;
}
else
{
tr[p<<1].rev^=1;
}
if(tr[p<<1|1].tag!=-1)
{
tr[p<<1|1].tag^=1;
}
else
{
tr[p<<1|1].rev^=1;
}
swap(tr[p<<1].lmax[0],tr[p<<1].lmax[1]);
swap(tr[p<<1].rmax[0],tr[p<<1].rmax[1]);
swap(tr[p<<1].max[0],tr[p<<1].max[1]);
swap(tr[p<<1|1].lmax[0],tr[p<<1|1].lmax[1]);
swap(tr[p<<1|1].rmax[0],tr[p<<1|1].rmax[1]);
swap(tr[p<<1|1].max[0],tr[p<<1|1].max[1]);
tr[p].rev=0;
}
}
void update(int p,int op,int l,int r)
{
push_down(p);
if(tr[p].l==l&&tr[p].r==r)
{
if(op==0||op==1)
{
tr[p].sum=op*(tr[p].r-tr[p].l+1);
tr[p].max[op]=tr[p].lmax[op]=tr[p].rmax[op]=tr[p].r-tr[p].l+1;
tr[p].max[op^1]=tr[p].lmax[op^1]=tr[p].rmax[op^1]=0;
tr[p].tag=op;
}
else if(op==2)
{
tr[p].sum=tr[p].r-tr[p].l+1-tr[p].sum;
tr[p].rev^=1;
swap(tr[p].lmax[0],tr[p].lmax[1]);
swap(tr[p].rmax[0],tr[p].rmax[1]);
swap(tr[p].max[0],tr[p].max[1]);
}
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(mid<l)
{
update(p<<1|1,op,l,r);
}
else if(mid>=r)
{
update(p<<1,op,l,r);
}
else
{
update(p<<1,op,l,mid);
update(p<<1|1,op,mid+1,r);
}
push_up(p);
}
int getSum(int p,int l,int r)
{
push_down(p);
if(tr[p].l==l&&tr[p].r==r)
{
return tr[p].sum;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(mid<l)
{
return getSum(p<<1|1,l,r);
}
else if(mid>=r)
{
return getSum(p<<1,l,r);
}
else
{
return getSum(p<<1,l,mid)+getSum(p<<1|1,mid+1,r);
}
}
treeNode getMax(int p,int l,int r)
{
push_down(p);
if(tr[p].l==l&&tr[p].r==r)
{
return tr[p];
}
int mid=(tr[p].l+tr[p].r)>>1;
if(mid<l)
{
return getMax(p<<1|1,l,r);
}
else if(mid>=r)
{
return getMax(p<<1,l,r);
}
else
{
treeNode ans;
treeNode lc=getMax(p<<1,l,mid);
treeNode rc=getMax(p<<1|1,mid+1,r);
ans.sum=lc.sum+rc.sum;
for(int i=0;i<=1;++i)
{
ans.lmax[i]=lc.lmax[i];
if(i==0)
{
if(lc.sum==0)
{
ans.lmax[i]+=rc.lmax[i];
}
}
else
{
if(lc.sum==lc.r-lc.l+1)
{
ans.lmax[i]+=rc.lmax[i];
}
}
ans.rmax[i]=rc.rmax[i];
if(i==0)
{
if(rc.sum==0)
{
ans.rmax[i]+=lc.rmax[i];
}
}
else
{
if(rc.sum==rc.r-rc.l+1)
{
ans.rmax[i]+=lc.rmax[i];
}
}
ans.max[i]=max(lc.rmax[i]+rc.lmax[i],max(lc.max[i],rc.max[i]));
}
return ans;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=m;++i)
{
int op,l,r;
cin>>op>>l>>r;
++l;
++r;
if(op==0)
{
update(1,0,l,r);
}
else if(op==1)
{
update(1,1,l,r);
}
else if(op==2)
{
update(1,2,l,r);
}
else if(op==3)
{
cout<<getSum(1,l,r)<<endl;
}
else
{
cout<<getMax(1,l,r).max[1]<<endl;
}
}
}