steveyang137 @ 2024-07-22 10:04:49
先放一下我的程序作为参考。 注意cover和flip之间的关系:cover时清空flip标记,flip时不清空cover标记,因此如果有两个标签,cover必在flip之前发生。 而且,由于cover后可能还有flip,所以 不要清空flip tag!
总之看看我的代码和你的实现有什么出入吧
void pushdown(int p,int l,int r) {
int mid=l+r>>1;
if(seg[p].cover_tag!=-1) {
seg[p<<1].tot=seg[p].cover_tag*(mid-l+1);
seg[p<<1|1].tot=seg[p].cover_tag*(r-mid);
seg[p<<1].cover_tag=seg[p<<1|1].cover_tag=seg[p].cover_tag;
seg[p<<1].lmx=seg[p<<1].rmx=seg[p<<1].mx=(mid-l+1)*seg[p].cover_tag;
seg[p<<1].lmx0=seg[p<<1].rmx0=seg[p<<1].mx0=(mid-l+1)*!seg[p].cover_tag;
seg[p<<1|1].lmx=seg[p<<1|1].rmx=seg[p<<1|1].mx=(r-mid)*seg[p].cover_tag;
seg[p<<1|1].lmx0=seg[p<<1|1].rmx0=seg[p<<1|1].mx0=(r-mid)*!seg[p].cover_tag;
seg[p<<1].flip_tag=seg[p<<1|1].flip_tag=0;
seg[p].cover_tag=-1;
// seg[p].flip_tag=0;
}
if(seg[p].flip_tag) {
seg[p<<1].tot=mid-l+1-seg[p<<1].tot;
seg[p<<1].flip_tag^=1;
// seg[p<<1].cover_tag^=1;
swap(seg[p<<1].lmx,seg[p<<1].lmx0);
swap(seg[p<<1].rmx,seg[p<<1].rmx0);
swap(seg[p<<1].mx,seg[p<<1].mx0);
seg[p<<1|1].tot=r-mid-seg[p<<1|1].tot;
seg[p<<1|1].flip_tag^=1;
// seg[p<<1|1].cover_tag^=1;
swap(seg[p<<1|1].lmx,seg[p<<1|1].lmx0);
swap(seg[p<<1|1].rmx,seg[p<<1|1].rmx0);
swap(seg[p<<1|1].mx,seg[p<<1|1].mx0);
seg[p].flip_tag=0;
}
}
void modify(int p,int l,int r,int s,int t,int x) {
if(s<=l&&r<=t) {
if(x==0) seg[p]={0,0,0,0,0,0,r-l+1,r-l+1,r-l+1,seg[p].len};
else if(x==1) seg[p]={r-l+1,1,0,r-l+1,r-l+1,r-l+1,0,0,0,seg[p].len};
else {
seg[p].tot=r-l+1-seg[p].tot;
seg[p].flip_tag^=1;
swap(seg[p].lmx,seg[p].lmx0);
swap(seg[p].rmx,seg[p].rmx0);
swap(seg[p].mx,seg[p].mx0);
}
return;
}
pushdown(p,l,r);
int mid=l+r>>1;
if(s<=mid) modify(p<<1,l,mid,s,t,x);
if(mid<t) modify(p<<1|1,mid+1,r,s,t,x);
seg[p]=merge(seg[p<<1],seg[p<<1|1]);
return;
}
by yanbinmu @ 2024-10-19 12:10:51
Orz