wownmsl1 @ 2024-11-07 16:16:47
我在settag里设置了:变1的tag是1,变0的tag是2,取反的tag是3。
这个tag我理解的是:遇到要对孩子节点进行修改或者查询时才使用。
所以都是先对这个点进行修改后,再看tag修改成什么。
所以我在对本节点进行取反操作(即op==3)时:先修改该节点,再修改tag,
如果tag==1,即本来要全变成1,那么取反就是全变成0,于是我把这个点的tag=2(变0的tag是2)。
如果tag==2,即本来要全变成0,那么取反就是全变成1,于是我把这个点的tag=1(变1的tag是1)。
如果tag==3,即本来要全取反,那么取反再取反就是什么也没有做,于是我把这个点的tag=0。
如果tag==0,即本来什么也没有做,那么就进行取反,于是我把这个点的tag=3(取反的tag是3)。
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int sum,z0,y0,m0,z1,y1,m1,cd;
};
node tree[400010];
int tag[400005],num[400005];
int ls(int p)
{
return p*2;
}
int rs(int p)
{
return p*2+1;
}
void push_up(int p)
{
tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
tree[p].m0=max(tree[ls(p)].m0,max(tree[rs(p)].m0,tree[ls(p)].y0+tree[rs(p)].z0));
tree[p].m1=max(tree[ls(p)].m1,max(tree[rs(p)].m1,tree[ls(p)].y1+tree[rs(p)].z1));
if(tree[ls(p)].cd==tree[ls(p)].z0)
tree[p].z0=tree[ls(p)].cd+tree[rs(p)].z0;
else
tree[p].z0=tree[ls(p)].z0;
if(tree[ls(p)].cd==tree[ls(p)].z1)
tree[p].z1=tree[ls(p)].cd+tree[rs(p)].z1;
else
tree[p].z1=tree[ls(p)].z1;
if(tree[rs(p)].y0==tree[rs(p)].cd)
tree[p].y0=tree[rs(p)].y0+tree[ls(p)].y0;
else
tree[p].y0=tree[rs(p)].y0;
if(tree[rs(p)].y1==tree[rs(p)].cd)
tree[p].y1=tree[rs(p)].y1+tree[ls(p)].y1;
else
tree[p].y1=tree[rs(p)].y1;
}
void build(int p,int z,int y)
{
if(z==y)
{
tree[p].cd=1;
tree[p].sum=num[z];
if(tree[p].sum)
{
tree[p].m0=0;
tree[p].z0=0;
tree[p].y0=0;
tree[p].m1=1;
tree[p].z1=1;
tree[p].y1=1;
}
else
{
tree[p].m0=1;
tree[p].z0=1;
tree[p].y0=1;
tree[p].m1=0;
tree[p].z1=0;
tree[p].y1=0;
}
return ;
}
tree[p].cd=y-z+1;
int mid=(z+y)/2;
build(ls(p),z,mid);
build(rs(p),mid+1,y);
push_up(p);
}
void settag(int p,int z,int y,int op)
{
if(op==1)
{
tree[p].sum=tree[p].cd;
tree[p].m0=0;
tree[p].z0=0;
tree[p].y0=0;
tree[p].m1=tree[p].cd;
tree[p].z1=tree[p].cd;
tree[p].y1=tree[p].cd;
tag[p]=op;
}
else if(op==2)
{
tree[p].sum=0;
tree[p].m0=tree[p].cd;
tree[p].z0=tree[p].cd;
tree[p].y0=tree[p].cd;
tree[p].m1=0;
tree[p].z1=0;
tree[p].y1=0;
tag[p]=op;
}
else if(op==3)
{
tree[p].sum=tree[p].cd-tree[p].sum;
swap(tree[p].m0,tree[p].m1);
swap(tree[p].z0,tree[p].z1);
swap(tree[p].y0,tree[p].y1);
if(tag[p]==0)
tag[p]=3;
else if(tag[p]==1)
tag[p]=2;
else if(tag[p]==2)
tag[p]=1;
else if(tag[p]==3)
tag[p]=0;
}
}
void push_down(int p,int z,int y)
{
if(tag[p])
{
int mid=(z+y)/2;
settag(ls(p),z,mid,tag[p]);
settag(rs(p),mid+1,y,tag[p]);
tag[p]=0;
}
}
void update(int p,int z,int y,int l,int r,int op)
{
if(z>=l&&y<=r)
{
settag(p,z,y,op);
return ;
}
push_down(p,z,y);
int mid=(z+y)/2;
if(mid>=l)
update(ls(p),z,mid,l,r,op);
if(mid+1<=r)
update(rs(p),mid+1,y,l,r,op);
push_up(p);
}
int search1(int p,int z,int y,int l,int r)
{
if(z>=l&&y<=r)
return tree[p].sum;
push_down(p,z,y);
int mid=(z+y)/2;
int sum=0;
if(mid>=l)
sum+=search1(ls(p),z,mid,l,r);
if(mid+1<=r)
sum+=search1(rs(p),mid+1,y,l,r);
return sum;
}
node search2(int p,int z,int y,int l,int r)
{
node l1={0,0,0,0,0,0,0,0},l2,l3;
l2=l1;
if(z>=l&&y<=r)
return tree[p];
push_down(p,z,y);
int mid=(z+y)/2;
if(mid>=l)
l1=search2(ls(p),z,mid,l,r);
if(mid+1<=r)
l2=search2(rs(p),mid+1,y,l,r);
if(mid<l)
return l2;
if(mid+1>r)
return l1;
l3.cd=l1.cd+l2.cd;
if(l1.z1==l1.cd)
l3.z1=l1.z1+l2.z1;
else
l3.z1=l1.z1;
if(l2.y1==l2.cd)
l3.y1=l2.y1+l1.y1;
else
l3.y1=l1.y1;
l3.m1=max(l1.m1,max(l2.m1,l1.y1+l2.z1));
return l3;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",num+i);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
x++;
y++;
if(op==0)
{
update(1,1,n,x,y,2);
}
else if(op==1)
update(1,1,n,x,y,1);
else if(op==2)
update(1,1,n,x,y,3);
else if(op==3)
printf("%d\n",search1(1,1,n,x,y));
else if(op==4)
{
node ans;
ans=search2(1,1,n,x,y);
printf("%d\n",max(ans.z1,max(ans.y1,ans.m1)));//
}
}
}
by MYLHF @ 2024-11-07 17:36:06
本来一个就能过
by wownmsl1 @ 2024-11-12 14:10:23
@MYLHF 大佬,那我的代码是哪里出问题了呢?