求py的写法

Xile @ 2024-09-30 09:08:13

by Xile @ 2024-09-30 09:16:32

如果可以的话可以给我线段树的写法

by NightDiver @ 2024-09-30 14:11:03

class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.z = [0] * (4 * n)
        self.col = [0] * (4 * n)

    def update(self, rt):
        self.z[rt] = self.z[rt * 2] + self.z[rt * 2 + 1]

    def color(self, l, r, rt, v):
        self.z[rt] = (r - l + 1) * v
        self.col[rt] = v

    def push_col(self, l, r, rt):
        if self.col[rt]:
            m = (l + r) // 2
            self.color(l, m, rt * 2, self.col[rt])
            self.color(m + 1, r, rt * 2 + 1, self.col[rt])
            self.col[rt] = 0

    def build(self, l, r, rt):
        if l == r:
            self.z[rt] = 0
            return
        m = (l + r) // 2
        self.build(l, m, rt * 2)
        self.build(m + 1, r, rt * 2 + 1)
        self.update(rt)

    def modify(self, l, r, rt, nowl, nowr, v):
        if nowl <= l and r <= nowr:
            self.color(l, r, rt, v)
            return
        m = (l + r) // 2
        self.push_col(l, r, rt)
        if nowl <= m:
            self.modify(l, m, rt * 2, nowl, nowr, v)
        if m < nowr:
            self.modify(m + 1, r, rt * 2 + 1, nowl, nowr, v)
        self.update(rt)

    def query(self, l, r, rt, nowl, nowr):
        if nowl <= l and r <= nowr:
            return self.z[rt]
        m = (l + r) // 2
        self.push_col(l, r, rt)
        result = 0
        if nowl <= m:
            result += self.query(l, m, rt * 2, nowl, nowr)
        if m < nowr:
            result += self.query(m + 1, r, rt * 2 + 1, nowl, nowr)
        return result

def read_ints():
    return list(map(int, input().split()))

n, m = read_ints()
segment_tree = SegmentTree(n)
segment_tree.build(0, n, 1)

for _ in range(m):
    a, b = read_ints()
    segment_tree.modify(0, n, 1, a, b, 1)

result = n - segment_tree.query(0, n, 1, 0, n) + 1
print(result)

by NightDiver @ 2024-09-30 14:11:49

@Xile 儿子不用谢谢爸爸

by Xile @ 2024-11-11 09:04:49

@NightDiver 谢谢爸爸