1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
# 线段树的节点类
class SegTreeNode:
def __init__(self, left=-1, right=-1, val=0, lazy_tag=None, leftNode=None, rightNode=None):
self.left = left # 区间左边界
self.right = right # 区间右边界
self.mid = left + (right - left) // 2
self.leftNode = leftNode # 区间左节点
self.rightNode = rightNode # 区间右节点
self.val = val # 节点值(区间值)
self.lazy_tag = lazy_tag # 区间问题的延迟更新标记
# 线段树类
class SegmentTree:
# 初始化线段树接口
def __init__(self, function):
self.tree = SegTreeNode(0, int(1e9))
self.function = function # function 是一个函数,左右区间的聚合方法
# 区间更新接口:将区间为 [q_left, q_right] 上的元素值修改为 val
def update_interval(self, q_left, q_right, val):
self.__update_interval(q_left, q_right, val, self.tree)
# 区间查询接口:查询区间为 [q_left, q_right] 的区间值
def query_interval(self, q_left, q_right):
return self.__query_interval(q_left, q_right, self.tree)
# 以下为内部实现方法
# 区间更新实现方法
def __update_interval(self, q_left, q_right, val, node):
if node.left >= q_left and node.right <= q_right: # 节点所在区间被 [q_left, q_right] 所覆盖
node.lazy_tag = val # 将当前节点的延迟标记标记为 val
interval_size = (node.right - node.left + 1) # 当前节点所在区间大小
node.val = val * interval_size # 当前节点所在区间每个元素值改为 val
return
if node.right < q_left or node.left > q_right: # 节点所在区间与 [q_left, q_right] 无关
return
self.__pushdown(node) # 向下更新节点所在区间的左右子节点的值和懒惰标记
if q_left <= node.mid: # 在左子树中更新区间值
self.__update_interval(q_left, q_right, val, node.leftNode)
if q_right > node.mid: # 在右子树中更新区间值
self.__update_interval(q_left, q_right, val, node.rightNode)
self.__pushup(node)
# 区间查询实现方法:在线段树的 [left, right] 区间范围中搜索区间为 [q_left, q_right] 的区间值
def __query_interval(self, q_left, q_right, node):
if node.left >= q_left and node.right <= q_right: # 节点所在区间被 [q_left, q_right] 所覆盖
return node.val # 直接返回节点值
if node.right < q_left or node.left > q_right: # 节点所在区间与 [q_left, q_right] 无关
return 0
self.__pushdown(node) # 向下更新节点所在区间的左右子节点的值和懒惰标记
res_left = 0 # 左子树查询结果
res_right = 0 # 右子树查询结果
if q_left <= node.mid: # 在左子树中查询
res_left = self.__query_interval(q_left, q_right, node.leftNode)
if q_right > node.mid: # 在右子树中查询
res_right = self.__query_interval(q_left, q_right, node.rightNode)
return self.function(res_left, res_right) # 返回左右子树元素值的聚合计算结果
# 向上更新实现方法:更新 node 节点区间值 等于 该节点左右子节点元素值的聚合计算结果
def __pushup(self, node):
if node.leftNode and node.rightNode:
node.val = self.function(node.leftNode.val, node.rightNode.val)
# 向下更新实现方法:更新 node 节点所在区间的左右子节点的值和懒惰标记
def __pushdown(self, node):
if node.leftNode is None:
node.leftNode = SegTreeNode(node.left, node.mid)
if node.rightNode is None:
node.rightNode = SegTreeNode(node.mid + 1, node.right)
lazy_tag = node.lazy_tag
if node.lazy_tag is None:
return
node.leftNode.lazy_tag = lazy_tag # 更新左子节点懒惰标记
left_size = (node.leftNode.right - node.leftNode.left + 1)
node.leftNode.val = lazy_tag * left_size # 更新左子节点值
node.rightNode.lazy_tag = lazy_tag # 更新右子节点懒惰标记
right_size = (node.rightNode.right - node.rightNode.left + 1)
node.rightNode.val = lazy_tag * right_size # 更新右子节点值
node.lazy_tag = None # 更新当前节点的懒惰标记
class CountIntervals:
def __init__(self):
self.STree = SegmentTree(lambda x, y: x + y)
self.left = 10 ** 9
self.right = 0
def add(self, left: int, right: int) -> None:
self.STree.update_interval(left, right, 1)
def count(self) -> int:
return self.STree.query_interval(0, int(1e9))
# Your CountIntervals object will be instantiated and called as such:
# obj = CountIntervals()
# obj.add(left,right)
# param_2 = obj.count()
|