区间重置线段树的简单应用,这里给出模板,请自行搜索学习:

"""所有下标都从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的就是我们的结果,请读者自行实现,应该是正确的。