题目
给你一个无限长的数组,初始的时候都为0,有3种操作:
操作1是把给定区间[l,r]设为1。
操作2是把给定区间[l,r]设为0。[l,r]">
操作3把给定区间[l,r]的0,1反转[l,r]">。
l,r<=1018
一共n(n<=105)个操作,每次操作后要输出最小位置的0。
解法
看到维护区间,想到线段树。
看到数据范围,想到把操作离线然后离散化。
然后再yy一下合并状态:
每个节点维护两个信息:
min0表示该区间最小位置的0,初始值为l (当时错在了这里)。
min1表示该区间最小位置的1,初始值为inf。
合并时左右取最小即可
操作
- min0=inf,min1=l
- min0=l,min1=inf
- 交换min0,min1
通过懒标记维护。
一些细节问题
- 离散化时要把r+1也一同离散化,否则 (r0,l1)这段区间会遗失。(当时错在了这里*2)
- pushdown的时候可能同时会有反转和修改操作,为了防止顺序出错,要做点处理(当时错在了这里*3)
- 反转标记在前,修改操作在后:可以直接无视掉反转标记。所以要在打标记前清除反转标记。
- 反转标记在后,修改操作在前:必须先处理修改操作。所以pushdown函数里修改要写在反转的前面
- 数组要开n*3*4(每个操作最多有三个数,线段树空间要*4)(当时错在了这里*4)
代码
#include
#include
#include
#include