title
一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：
- 同一组的
k位观众坐在 同一排座位，且座位连续 。 k位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。
由于观众非常挑剔，所以：
- 只有当一个组里所有成员座位的排数都 小于等于
maxRow，这个组才能订座位。每一组的maxRow可能 不同 。 - 如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
请你实现 BookMyShow 类：
BookMyShow(int n, int m)，初始化对象，n是排数，m是每一排的座位数。int[] gather(int k, int maxRow)返回长度为2的数组，表示k个成员中 第一个座位 的排数和座位编号，这k位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的r和c满足第r排中[c, c + k - 1]的座位都是空的，且r <= maxRow。如果 无法 安排座位，返回[]。boolean scatter(int k, int maxRow)如果组里所有k个成员 不一定 要坐在一起的前提下，都能在第0排到第maxRow排之间找到座位，那么请返回true。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有k个成员的座位，请返回false。
示例 1：
输入：
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
输出：
[null, [0, 0], [], true, false]
解释：
BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。
bms.gather(4, 0); // 返回 [0, 0]
// 这一组安排第 0 排 [0, 3] 的座位。
bms.gather(2, 0); // 返回 []
// 第 0 排只剩下 1 个座位。
// 所以无法安排 2 个连续座位。
bms.scatter(5, 1); // 返回 True
// 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。
bms.scatter(5, 1); // 返回 False
// 总共只剩下 2 个座位。
提示：
1 <= n <= 5 * 1041 <= m, k <= 1090 <= maxRow <= n - 1gather和scatter总 调用次数不超过5 * 104次。
solution
线段树模板，重点是求区间内第一个>= val的位置，这个是线段树上进行二分，是个range max操作
from typing import Any
# 线段树的节点类
class STNode:
def __init__(self, left=-1, right=-1, val=0):
self.left = left # 区间左边界
self.right = right # 区间右边界
self.mid = (left + right) >> 1
self.leftNode = None # 区间左节点
self.rightNode = None # 区间右节点
self.val = val # 节点值（区间值）
self.lazy_tag = None # 区间问题的延迟更新标记
def __repr__(self):
return f"{self.left}:{self.right} = {self.val}"
# 线段树类
class SegmentTree:
def build(self, left=0, right=int(1e9)):
# 注意right不能小于查询边界，这里更新查询最大只能[left,right]
self.root = STNode(left, right)
def build_with_data(self, data=[]):
self.data = data
# 注意right不能小于查询边界，这里更新查询最大只能[left,right]
def create_tree(left, right) -> STNode: # 构建[left, right]的树
node = STNode(left, right)
if left == right:
node.val = data[left] # 到达叶节点
else:
mid = (left + right) >> 1
# 构建左右子树
# print(left, mid, right, node)
node.leftNode, node.rightNode = create_tree(left, mid), create_tree(mid + 1, right)
self.merge(node)
return node
self.root = create_tree(0, len(data) - 1)
# collect 左区间和右区间的聚合方法；传入左区间和右区间，返回一个任意值作为两区间的聚合结果
def collect(self, a, b):
# 取sum
# return a + b
# 取max
return max(a,b)
# 取min
# return max(a,b)
# 用于加lazy标记的，实际上是当前val变下，然后加的标记影响子节点
def lazy_update(self, node: STNode, lazy: Any):
# 源头是update_interval时调用，然后pushdown时有lazy_tag就下推下推，如果没有update_interval就没有lazy_tag了
meta_size = (node.right - node.left + 1) # (r - l + 1)为此区间的元线段数
# 区间替换成val, 不需要累加标记
# node.val = meta_size * lazy
# 区间+val, 需要累加标记
node.val += meta_size * lazy
# 累加标记
# node.lazy_tag = node.lazy_tag + lazy if node.lazy_tag is not None else lazy
# 不累加标记
node.lazy_tag = lazy
# collect区间合并
def merge(self, node):
node.val = self.collect(node.leftNode.val, node.rightNode.val)
def __create_child_nodes(self, node: STNode):
if not node.leftNode:
node.leftNode = STNode(node.left, node.mid)
if not node.rightNode:
node.rightNode = STNode(node.mid + 1, node.right)
# 向下更新 node 节点所在区间的左右子节点的值和懒惰标记
# 实际是把当前节点的lazy flag去掉，转化并加到下面节点上去
def __pushdown(self, node):
self.__create_child_nodes(node)
if node.lazy_tag is not None:
if node.left != node.right:
self.lazy_update(node.leftNode, node.lazy_tag)
self.lazy_update(node.rightNode, node.lazy_tag)
# 如果是叶子节点已经由父节点更新这个叶子节点值了
node.lazy_tag = None # 更新当前节点的懒惰标记
# 单点更新，将 nums[i] 更改为 val
def update_point(self, i, val):
# 单点更新，将 nums[i] 更改为 val。node 节点的区间为 [node.left, node.right]
def dfs(i, val, node):
# 单点更新只改了个点的val，不需要考虑lazy flag
if node.left == node.right:
self.lazy_update(node, val)
return
self.__pushdown(node)
if i <= node.mid: # 在左子树中更新节点值
dfs(i, val, node.leftNode)
else: # 在右子树中更新节点值
dfs(i, val, node.rightNode)
self.merge(node)
dfs(i, val, self.root)
# 区间查询，查询区间为 [q_left, q_right] 的区间值
def query_interval(self, left, right):
# 区间查询，在线段树的 [left, right] 区间范围中搜索区间为 [q_left, q_right] 的区间值
def dfs(q_left, q_right, node):
if q_right < node.left or q_left > node.right:
return 0
if q_left <= node.left and node.right <= q_right: # 区间就是想要的区间
return node.val # 直接返回节点值
self.__pushdown(node)
res_left = 0
res_right = 0
if q_left <= node.mid: # 在左子树中查询
res_left = dfs(q_left, q_right, node.leftNode)
if q_right > node.mid: # 在右子树中查询
res_right = dfs(q_left, q_right, node.rightNode)
return self.collect(res_left, res_right) # 返回左右子树元素值的聚合计算结果
return dfs(left, right, self.root)
# 求[left,right]区间的大于等于val的第一个位置, 二分
def query_first_not_less_val(self, left, right, val):
# 区间查询，在线段树的 [left, right] 区间范围中搜索区间为 [q_left, q_right] 的区间值
def dfs(q_left, q_right, node):
# 没关系 就return
if q_right < node.left or q_left > node.right:
return -1
# 有关系的话，可提前看是否有必要深入
if q_left <= node.left and node.right <= q_right: # 区间就是想要的区间
# 如果max value都小于val了, 没必要深入下去了
if node.val < val:
return -1
# 到叶子节点了
if node.left == node.right:
if node.val < val:
return -1
return node.left
self.__pushdown(node)
res_left = -1
if q_left <= node.mid: # 在左子树中查询
res_left = dfs(q_left, q_right, node.leftNode)
if res_left != -1:
return res_left
res_right = -1
if q_right > node.mid: # 在右子树中查询
res_right = dfs(q_left, q_right, node.rightNode)
return self.collect(res_left, res_right) # 返回左右子树元素值的聚合计算结果
return dfs(left, right, self.root)
# 区间更新，将区间为 [q_left, q_right] 上的元素值修改为 val
def update_interval(self, left, right, val):
# 区间更新
def dfs(q_left, q_right, val, node):
self.__pushdown(node) # 向下更新节点所在区间的左右子节点的值和懒惰标记
if q_left <= node.left and node.right <= q_right: # 当前区间都是要更新的
self.lazy_update(node, val)
return
if q_left <= node.mid: # 在左子树中更新区间值
dfs(q_left, q_right, val, node.leftNode)
if q_right > node.mid: # 在右子树中更新区间值
dfs(q_left, q_right, val, node.rightNode)
self.merge(node)
dfs(left, right, val, self.root)
class BookMyShow:
def __init__(self, n: int, m: int):
self.n = n
self.m = m
self.max_st = SegmentTree()
self.max_st.collect = lambda a, b: max(a, b)
self.max_st.build_with_data([m for _ in range(n)])
self.sum_st = SegmentTree()
self.sum_st.collect = lambda a, b: a + b
self.sum_st.build_with_data([m for _ in range(n)])
def add(self, i, val):
self.max_st.update_point(i, val)
self.sum_st.update_point(i, val)
def gather(self, k: int, maxRow: int) -> List[int]:
res = self.max_st.query_first_not_less_val(0, maxRow, k)
if res < 0:
return []
cur_val = self.max_st.query_interval(res, res)
self.add(res, -k)
return [res, self.m - cur_val]
def scatter(self, k: int, maxRow: int) -> bool:
cur_sum = self.sum_st.query_interval(0, maxRow)
if cur_sum < k:
return False
first_index = self.max_st.query_first_not_less_val(0, maxRow, 1)
i = first_index
while k > 0:
cur = self.max_st.query_interval(i, i)
if cur > k:
self.add(i, -k)
k = 0
else:
self.add(i, -cur)
k -= cur
i += 1
return True