由于区间推平标记flag
,和区间反转标记rev
具有不能共存性,故总结一下在做题中遇到该类问题时的解决方法
特殊之处在于两点:
modify时:如果之前区间有rev
,现在新来一个add
,那么之前的rev
就清零
如果之前区间有add
,现在新来一个rev
,那么之前的add
就取反
pushdown 时:
此时我们知道,flag
一定比rev
先来,
所以先处理flag
标记,看左右两个儿子是否有rev
标记,如果有就清零
再处理rev
标记,看两个儿子是否有flag
标记,如果有,就让它们的flag
分别取反(^=1
),rev
标记不必下传
如果没有,必须下传rev
标记
其他的处理方式就和之前的题目一样了,重点记住上面所述的特殊情况即可
看一段示例代码,出自题目CF817F MEX Queries:
inline void pushdown(int l,int r,int rt)
{
int mid=(l+r)>>1;
if(tag[rt]!=-1) //如果有tag,那么就清空rev
{
tag[rt<<1]=tag[rt];
tag[rt<<1|1]=tag[rt];
rev[rt<<1]=0;
rev[rt<<1|1]=0;
if(tag[rt])
{
sum[rt<<1]=mid-l+1;
sum[rt<<1|1]=r-mid;
}
else
{
sum[rt<<1]=0;
sum[rt<<1|1]=0;
}
tag[rt]=-1;
}
if(rev[rt]) //如果有rev,那么如果有tag,就将tag^1,否则将rev^1
{
if(tag[rt<<1]!=-1) tag[rt<<1]^=1;
else rev[rt<<1]^=1;
if(tag[rt<<1|1]!=-1) tag[rt<<1|1]^=1;
else rev[rt<<1|1]^=1;
sum[rt<<1]=mid-l+1-sum[rt<<1];
sum[rt<<1|1]=r-mid-sum[rt<<1|1];
rev[rt]=0;
}
}
orz