h1910819075 @ 2021-10-27 11:21:22
rt,我的线段树中的懒标记就是取反和翻转的标记,事实告诉我这样是不行的,可是我想不通为什么不能使用同一个变量,在我看来,因为翻转的标记的一定是优先取反标记的,所以在有翻转的标记的时候直接覆盖就好了,有取反标记的时候就也会覆盖翻转的标记。使用同一个变量有什么不对的吗?QAQ,求解。
by SSerxhs @ 2021-10-27 11:25:54
by h1910819075 @ 2021-10-27 11:34:15
@SSerxhs 翻转就是全部变为0或者1
by h1910819075 @ 2021-10-27 11:48:04
应该用推翻来形容?反正大概意思就是全部变为0或1的状态。唉~为什么不能同一个变量,现在我还没有弄清,QAQ
by h1910819075 @ 2021-10-27 11:50:43
重点是我使用同一个变量,要是全WA,我还能理解,TLE是什么鬼!
by zhiyangfan @ 2021-10-27 11:57:05
@h1910819075 能放一下代码吗?这道题属于是码农题,细节比较多,光靠您这样说可能不是很清楚qwq
by h1910819075 @ 2021-10-27 17:15:38
这是代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
struct point{
int L,R;
int lcnt,rcnt,sum,ma,lz;
int flcnt,frcnt,fsum,fma;
//sum是一段区间1的个数,ma是一段区间最长连续的1的个数;
}tree[N*4];
int n,m,a[N];
inline void push_up(int node)
{
int L=tree[node].L,R=tree[node].R;
int mid=(L+R)>>1;
int L_node=node<<1,R_node=node<<1|1;
tree[node].sum=tree[L_node].sum+tree[R_node].sum;
tree[node].ma=max(tree[L_node].rcnt+tree[R_node].lcnt,max(tree[L_node].ma,tree[R_node].ma));
if(tree[L_node].ma==mid-L+1)
tree[node].lcnt=tree[L_node].ma+tree[R_node].lcnt;
else
tree[node].lcnt=tree[L_node].lcnt;
if(tree[R_node].ma==R-mid)
tree[node].rcnt=tree[L_node].rcnt+tree[R_node].ma;
else
tree[node].rcnt=tree[R_node].rcnt;
//取反的区间
tree[node].fsum=tree[L_node].fsum+tree[R_node].fsum;
tree[node].fma=max(tree[L_node].frcnt+tree[R_node].flcnt,max(tree[L_node].fma,tree[R_node].fma));
if(tree[L_node].fma==mid-L+1)
tree[node].flcnt=tree[L_node].fma+tree[R_node].flcnt;
else
tree[node].flcnt=tree[L_node].flcnt;
if(tree[R_node].fma==R-mid)
tree[node].frcnt=tree[L_node].frcnt+tree[R_node].fma;
else
tree[node].frcnt=tree[R_node].frcnt;
}
inline void build(int node,int L,int R)
{
tree[node].L=L,tree[node].R=R;
tree[node].lz=-1;
if(L==R)
{
tree[node].lcnt=tree[node].rcnt=tree[node].sum=tree[node].ma=a[L];
tree[node].flcnt=tree[node].frcnt=tree[node].fsum=tree[node].fma=a[L]^1;
return ;
}
int mid=(L+R)>>1;
int L_node=node<<1,R_node=node<<1|1;
build(L_node,L,mid);
build(R_node,mid+1,R);
push_up(node);
}
inline void push_down(int node)
{
int L_node=node<<1,R_node=node<<1|1;
int mid=(tree[node].L+tree[node].R)>>1;
if(tree[node].lz==0)//下面的子节点要置为空房间
{
tree[L_node].lz=tree[R_node].lz=0;
tree[L_node].sum=tree[L_node].lcnt=tree[L_node].rcnt=tree[L_node].ma=0;
tree[R_node].sum=tree[R_node].lcnt=tree[R_node].rcnt=tree[R_node].ma=0;
tree[L_node].fsum=tree[L_node].flcnt=tree[L_node].frcnt=tree[L_node].fma=mid-tree[node].L+1;
tree[R_node].fsum=tree[R_node].flcnt=tree[R_node].frcnt=tree[R_node].fma=tree[node].R-mid;
}
else if(tree[node].lz==1)//对下面的字节点要置为满房间;
{
tree[L_node].lz=tree[R_node].lz=1;
tree[L_node].sum=tree[L_node].lcnt=tree[L_node].rcnt=tree[L_node].ma=mid-tree[node].L+1;
tree[R_node].sum=tree[R_node].lcnt=tree[R_node].rcnt=tree[R_node].ma=tree[node].R-mid;
tree[L_node].fsum=tree[L_node].flcnt=tree[L_node].frcnt=tree[L_node].fma=0;
tree[R_node].fsum=tree[R_node].flcnt=tree[R_node].frcnt=tree[R_node].fma=0;
}
else if(tree[node].lz==2)
{
tree[L_node].lz=tree[R_node].lz=2;
int tlcnt=tree[L_node].lcnt,trcnt=tree[L_node].rcnt,tma=tree[L_node].ma,tsum=tree[L_node].sum;
tree[L_node].lcnt=tree[L_node].flcnt;tree[L_node].rcnt=tree[L_node].frcnt;
tree[L_node].ma=tree[L_node].fma,tree[L_node].sum=tree[L_node].fsum;
tree[L_node].flcnt=tlcnt;tree[L_node].frcnt=trcnt;
tree[L_node].fma=tma,tree[L_node].fsum=tsum;
tlcnt=tree[R_node].lcnt,trcnt=tree[R_node].rcnt,tma=tree[R_node].ma,tsum=tree[R_node].sum;
tree[R_node].lcnt=tree[R_node].flcnt;tree[R_node].rcnt=tree[R_node].frcnt;
tree[R_node].ma=tree[R_node].fma,tree[R_node].sum=tree[R_node].fsum;
tree[R_node].flcnt=tlcnt;tree[R_node].frcnt=trcnt;
tree[R_node].fma=tma,tree[R_node].fsum=tsum;
}
tree[node].lz=-1;
}
inline void modify(int node,int L,int R,int x)
{
if(L<=tree[node].L&&tree[node].R<=R)
{
if(x==0)//全部置为0
{
tree[node].lcnt=tree[node].rcnt=tree[node].ma=tree[node].sum=0;
tree[node].flcnt=tree[node].frcnt=tree[node].fma=tree[node].fsum=tree[node].R-tree[node].L+1;
}
else if(x==1)//全部置为1
{
tree[node].lcnt=tree[node].rcnt=tree[node].ma=tree[node].sum=tree[node].R-tree[node].L+1;
tree[node].flcnt=tree[node].frcnt=tree[node].fma=tree[node].fsum=0;
}
else if(x==2)//全部取反
{
int tlcnt=tree[node].lcnt,trcnt=tree[node].rcnt,tma=tree[node].ma,tsum=tree[node].sum;
tree[node].lcnt=tree[node].flcnt;tree[node].rcnt=tree[node].frcnt;
tree[node].ma=tree[node].fma,tree[node].sum=tree[node].fsum;
tree[node].flcnt=tlcnt;tree[node].frcnt=trcnt;
tree[node].fma=tma,tree[node].fsum=tsum;
}
tree[node].lz=x;
return ;
}
push_down(node);
int mid=(tree[node].L+tree[node].R)>>1;
int L_node=node<<1,R_node=node<<1|1;
if(L<=mid)
modify(L_node,L,R,x);
if(R>mid)
modify(R_node,L,R,x);
push_up(node);
}
inline int query1(int node,int L,int R)
{
if(tree[node].L>=L&&tree[node].R<=R)
return tree[node].sum;
push_down(node);//父节点的内容传下去!!!
int mid=(tree[node].L+tree[node].R)>>1;
int ans=0;
if(L<=mid)
ans+=query1(node<<1,L,R);
if(R>mid)
ans+=query1(node<<1|1,L,R);
return ans;
}
inline int query2(int node,int L,int R)
{
if(tree[node].L<=L&&tree[node].R<=R)
return tree[node].ma;
push_down(node);//父节点的内容传下去!!!
int mid=(tree[node].L+tree[node].R)>>1;
if(L<=mid&&R>mid)
{
int ans=max(query2(node<<1,L,R),query2(node<<1|1,L,R));
int ans1=min(tree[node<<1].rcnt,mid-L+1)+min(tree[node<<1|1].rcnt,R-mid);
return max(ans,ans1);
}
else if(L<=mid)
return query2(node<<1,L,R);
else if(R>mid)
return query2(node<<1|1,L,R);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
while(m--)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
l++,r++;
if(op<=2)
modify(1,l,r,op);
else if(op==3)
printf("%d\n",query1(1,l,r));
else
printf("%d\n",query2(1,l,r));
//for(int i=1;i<=3*n;i++)
// printf("i=%d sum=%d lcnt=%d rcnt=%d ma=%d fsum=%d flcnt=%d frcnt=%d fma=%d \n",i,tree[i].sum,tree[i].lcnt,tree[i].rcnt,tree[i].ma,tree[i].fsum,tree[i].flcnt,tree[i].frcnt,tree[i].fma);
}
return 0;
}
by h1910819075 @ 2021-10-27 18:15:25
我明白为什么不能使用同一个变量了,为什么我的代码会TLE了,QAQ,太艰难了!