线段树解决填数字问题

问题背景

在做本周的算法作业时，遇到了一道令我感到十分棘手的题目。

如果按照传统的方法解决这道题目，似乎无法避免每一次找最长连续0序列时$O(n)$的复杂度（至少我没找到），如此一来总的复杂度至少会达到$O(n^2)$。根据我的直觉，这显然不会是这道题最佳的答案。终于，经历了将近一天的思考以及和chatgpt的对线，我采用线段树的思想设计出了一种复杂度为$O(nlogn)$的算法（本人太傻，勿喷）。

该算法的大致思路是：首先将原始数组从中点分成两部分，左边的部分作为原始数组的左子树，右半部分则作为右子树，之后再对这两半进行相同的操作，直到每个子数组都不可再分，按照如此方法构造出原始数组的线段树。对于线段树中的每一个节点，它会保存自己的左边界left、右边界right和所包含的最长连续为0序列的长度length。

之后，每进行一次操作，首先从线段树的根节点开始递归搜索与左右子节点的length都不同的节点，该节点就是代表目前最长连续为0序列的节点（因为它的左右子节点length都和它自己不同，说明它的左右子树没有被更新过，也就是说这段序列的值都为初始的0），找到该节点后，我们取它的中点作为本次操作修改数组值的索引，之后，再以该节点为根节点，递归更新后面所有节点的length为其左右子树length的最大值。重复以上操作直到数组被全部赋上新值。

伪代码实现

# 定义线段树节点
class TreeNode:
    def __init__(self, left, right):
        self.left = left
        self.right = right
        self.length = right - left + 1
        self.mid = (left + right) // 2
        self.value = 0  # 初始值为0

# 构建线段树
def build_segment_tree(left, right):
    if left == right:
        return TreeNode(left, right)
    mid = (left + right) // 2
    left_node = build_segment_tree(left, mid)
    right_node = build_segment_tree(mid + 1, right)
    return TreeNode(left, right)

def update_segment_tree(node, idx, value):
    if node.length == node.left.length:
        rs = update_segment_tree(node.left, idx, value)
    else if node.length == node.right.length:
        rs = update_segment_tree(node.right, idx, value)
    else:
        rs = node.mid
        update_segment_value(node, rs, value)
    node.length = max(node.left.length, node.right.length)
    return rs

# 更新线段树
def update_segment_value(node, idx, value):
    if node.left == node.right:
        node.value = value
        return
    if idx <= node.mid:
        update_segment_value(node.left, idx, value)
    else:
        update_segment_value(node.right, idx, value)
    node.length = max(node.left.length, node.right.length)

# 执行n次操作
def perform_operations(n):
    root = build_segment_tree(1, n)
    result = [0] * n
    for i in range(1, n + 1):
        max_length = root.length
        result_idx = root.mid
        result_idx = update_segment_tree(root, root.mid, i)
        result[result_idx] = i
       
    return result

操作示例

第一次操作

第二次操作