区间重置线段树的简单应用,这里给出模板,请自行搜索学习:
"""所有下标都从0开始"""
class LazySegmentTree:
def __init__(self, n: int):
self.n = n
self.sum = [0] * (self.n * 4)
self.reset_lazy = [-1] * (self.n * 4)
def doReset(self, o: int, l: int, r: int, v: int) -> None:
self.sum[o] = (r - l + 1) * v
self.reset_lazy[o] = v
def push_down(self, o: int, l: int, r: int) -> None:
left = 2 * o + 1
right = 2 * o + 2
if self.reset_lazy[o] != -1:
m = (l + r) // 2
v = self.reset_lazy[o]
self.doReset(left, l, m, v)
self.doReset(right, m + 1, r, v)
self.reset_lazy[o] = -1
def maintain(self, o: int) -> None:
left = 2 * o + 1
right = 2 * o + 2
self.sum[o] = self.sum[left] + self.sum[right]
def _reset_update(self, o: int, l: int, r: int, start: int, end: int, v: int) -> None:
if start <= l and r <= end:
self.doReset(o, l, r, v)
return
left = 2 * o + 1
right = 2 * o + 2
m = (l + r) // 2
self.push_down(o, l, r)
if m >= start:
self._reset_update(left, l, m, start, end, v)
if m < end:
self._reset_update(right, m + 1, r, start, end, v)
self.maintain(o)
def _query(self, o: int, l: int, r: int, start: int, end: int) -> int:
if start <= l and r <= end:
return self.sum[o]
m = (l + r) // 2
left = 2 * o + 1
right = 2 * o + 2
self.push_down(o, l, r)
res = 0
if m >= start:
res += self._query(left, l, m, start, end)
if m < end:
res += self._query(right, m + 1, r, start, end)
return res
def query(self, start: int, end: int) -> int:
return self._query(0, 0, self.n - 1, start, end)
def reset_update(self, start: int, end: int, v: int) -> None:
return self._reset_update(0, 0, self.n - 1, start, end, v)
有了这个类之后,里面的函数支持将闭区间
重置为某个值,这样我们只需要顺序重置即可。需要注意,题目给出的范围非常大,需要离散化。
主函数实现:
#记录操作 op = 0 启动 op = 1 禁用
ops = []
for _ in range(n):
lst = input().split()
if len(lst) == 2:
op = 0
ranges = lst[-1]
lst = ranges.split(",")
for x in lst:
if "-" in x:
a, b = x.split("-")
ops.append([op, int(a), int(b)])
else:
ops.append([op, int(x), int(x)])
else:
op = 1
ranges = lst[-1]
lst = ranges.split(",")
for x in lst:
if "-" in x:
a, b = x.split("-")
ops.append([op, int(a), int(b)])
else:
ops.append([op, int(x), int(x)])
st = set()
for op, l, r in ops:
st.add(l)
st.add(r)
st.add(l - 1)
st.add(r + 1)
sarr = list(sorted(st))
def rank(x: int) -> int:
return bisect_left(sarr, x)
st = LazySegmentTree(len(sarr) + 1)
for op, l, r in ops:
if op == 0:
st.reset_update(rank(l), rank(r), 1)
else:
st.reset_update(rank(l), rank(r), 0)
#然后不断的查单点
i = 0
res = []
while i <= len(sarr):
if st.query(i, i) == 0:
i += 1
continue
start = i
while i <= len(sarr) and st.query(i, i) == 1:
i += 1
#[start,i)是连续区间
res.append([sarr[start],sarr[i - 1]])
for l, r in res[:-1]:
if l == r:
print(l, end=",")
else:
print(f"{l}-{r}", end=",")
if res:
if res[-1][0] == res[-1][1]:
print(res[-1][0], end="")
else:
print(f"{res[-1][0]}-{res[-1][1]}", end="")
if not res:
print()
但是注意到只有一次查询,并且越往后的优先级越高,会覆盖掉前面的,那么我们可以使用差分数组,每次分配一个绝对值,这个是一个自增的,每次用了加一下,然后对于撤销,直接取这个值的负数,给他区间操作上,然后对于启动,直接用这个正数给区间操作上,这样就会覆盖掉之前的取消操作,然后最后收集的时候大于0的就是我们的结果,请读者自行实现,应该是正确的。