2025-08-21：分割正方形Ⅱ。用go语言，给你一个二维整数数组 squares，其中每个元素 [xi, yi, li] 表示一个与 x 轴平行的正方形：左下角坐标为 (xi, yi)，边长为 li。请寻找最小的实数 Y，使水平直线 y = Y 将所有正方形的并集划分成上下两部分，且上半部分的面积与下半部分的面积相等。正方形之间可能相互覆盖，重叠区域只计入一次。答案以绝对误差不超过 $10^{-5}$ 视为正确。

1 <= squares.length <= 5 * 10000。

squares[i] = [xi, yi, li]。

squares[i].length == 3。

0 <= xi, yi <= 1000000000。

1 <= li <= 1000000000。

所有正方形的总面积不超过 1000000000000000。

输入： squares = [[0,0,1],[2,2,1]]。

输出： 1.00000。

解释：

任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

题目来自力扣3454。

分步骤描述过程

1. 问题分析：
   给定多个与x轴平行的正方形（可能重叠），需要找到一条水平线y=Y，使得所有正方形并集被分成上下两部分，且上下面积相等（总面积的一半）。由于正方形可能重叠，重叠区域只算一次，因此需要计算并集的面积。

2. 离散化横坐标：

   • 提取所有正方形的左右边界（即xi和xi+li），排序并去重，得到离散化的横坐标数组xs。这些横坐标将x轴分成多个区间（线段树中的叶子节点），每个区间长度（xs[i+1]-xs[i]）作为线段树中该节点维护的底边长度。

3. 事件处理：

   • 为每个正方形生成两个事件：下边界（yi）处增加覆盖（delta=1），上边界（yi+li）处减少覆盖（delta=-1）。将所有事件按y坐标排序。

4. 线段树初始化：

   • 线段树每个节点维护一段横坐标区间[lx, rx]的信息：
     • minCover：该区间内被矩形覆盖的最小次数（实际上这里维护的是当前区间被覆盖的次数，但通过懒标记更新整个子树）。
     • minCoverLen：该区间内被覆盖次数等于minCover的底边长之和（用于计算未被覆盖的长度）。
     • todo：懒标记，表示子树需要增加的覆盖次数（用于延迟更新）。
   • 建树：初始化线段树，叶子节点的minCover为0（初始未被覆盖），minCoverLen为对应区间的长度（xs[i+1]-xs[i]）。

5. 扫描线过程：

   • 按y坐标从小到大处理事件（模拟从下往上扫描）：
     • 对于每个事件（y, lx, rx, delta），找到其对应的离散化区间[l, r]（l为lx在xs中的索引，r为rx在xs中的索引减1）。
     • 更新线段树：将区间[l, r]的覆盖次数增加delta（通过线段树的区间更新，包括懒标记处理）。
     • 更新后，根节点维护整个x轴区间的信息：minCover表示整个区间被覆盖的最小次数（实际上根节点的minCover就是整个区间的最小覆盖次数，但这里我们关心是否被覆盖过？实际上，根节点的minCover为0表示有部分区间未被覆盖，否则全部被覆盖至少一次）。
     • 计算当前被至少一个矩形覆盖的底边总长度sumLen：总长度（xs[-1]-xs[0]）减去未被覆盖的长度（即根节点minCover为0时，minCoverLen就是未被覆盖的长度，否则为0）。
     • 记录当前事件处理后的累计面积（totArea）和当前的sumLen（用于后续二分）。累计面积的计算：从上一次事件到当前事件的高度差（events[i+1].y - e.y）乘以当前的sumLen，得到这一段的面积，并累加到totArea。

6. 二分查找分割线：

   • 总面积为totArea（所有正方形并集的面积），目标是找到y=Y使得下半部分面积为totArea/2。
   • 在records中记录每个事件处理后的累计面积（当前事件之前的累计面积）和当前的sumLen（底边被覆盖的长度）。
   • 二分查找最后一个累计面积小于totArea/2的事件索引i（即records[i].area < totArea/2 <= records[i+1].area）。
   • 分割线Y的位置：从事件i对应的y坐标（events[i].y）开始，还需要上升的高度为（剩余面积差）除以（当前的底边被覆盖长度sumLen）。即： Y = events[i].y + (totArea/2 - records[i].area) / records[i].sumLen

7. 输出结果：
   计算得到的Y即为答案，要求绝对误差不超过1e-5。

时间复杂度和额外空间复杂度

• 时间复杂度：

  • 离散化（排序去重）：O(n log n)，n为正方形数量（最多2n个坐标）。
  • 事件排序：O(n log n)。
  • 线段树建树：O(n)（实际节点数最多4N，N为离散化后区间数）。
  • 线段树每次更新和查询：O(log n)（每次事件处理更新区间，最多2n次事件）。
  • 二分查找：O(log n)。
  • 总时间复杂度：O(n log n)。

• 额外空间复杂度：

  • 离散化数组xs：O(n)。
  • 事件数组events：O(n)。
  • 线段树：O(n)（节点数最多4N，N为离散化后区间数，最多2n个点，区间数最多2n-1）。
  • records数组：O(n)。
  • 总空间复杂度：O(n)。

注意：n为正方形数量（输入规模），但离散化后区间数最多为2n（去重后可能更少），因此线段树节点数为O(n)。所有操作都是基于n的多项式级别。

Go完整代码如下：

package mainimport ("fmt""math/bits""slices""sort"
)// 线段树每个节点维护一段横坐标区间 [lx, rx]
type seg []struct {l, r        intminCoverLen int // 区间内被矩形覆盖次数最少的底边长之和minCover    int // 区间内被矩形覆盖的最小次数todo        int // 子树内的所有节点的 minCover 需要增加的量，注意这可以是负数
}// 根据左右儿子的信息，更新当前节点的信息
func (t seg) maintain(o int) {lo, ro := &t[o<<1], &t[o<<1|1]mn := min(lo.minCover, ro.minCover)t[o].minCover = mnt[o].minCoverLen = 0if lo.minCover == mn { // 只统计等于 minCover 的底边长之和t[o].minCoverLen = lo.minCoverLen}if ro.minCover == mn {t[o].minCoverLen += ro.minCoverLen}
}// 仅更新节点信息，不下传懒标记 todo
func (t seg) do(o, v int) {t[o].minCover += vt[o].todo += v
}// 下传懒标记 todo
func (t seg) spread(o int) {v := t[o].todoif v != 0 {t.do(o<<1, v)t.do(o<<1|1, v)t[o].todo = 0}
}// 建树
func (t seg) build(xs []int, o, l, r int) {t[o].l, t[o].r = l, rt[o].todo = 0if l == r {t[o].minCover = 0t[o].minCoverLen = xs[l+1] - xs[l]return}m := (l + r) >> 1t.build(xs, o<<1, l, m)t.build(xs, o<<1|1, m+1, r)t.maintain(o)
}// 区间更新
func (t seg) update(o, l, r, v int) {if l <= t[o].l && t[o].r <= r {t.do(o, v)return}t.spread(o)m := (t[o].l + t[o].r) >> 1if l <= m {t.update(o<<1, l, r, v)}if m < r {t.update(o<<1|1, l, r, v)}t.maintain(o)
}// 代码逻辑同 850 题，增加一个 records 数组记录关键数据
func separateSquares(squares [][]int) float64 {m := len(squares) * 2xs := make([]int, 0, m)type event struct{ y, lx, rx, delta int }events := make([]event, 0, m)for _, sq := range squares {lx, y, l := sq[0], sq[1], sq[2]rx := lx + lxs = append(xs, lx, rx)events = append(events, event{y, lx, rx, 1}, event{y + l, lx, rx, -1})}// 排序去重，方便离散化slices.Sort(xs)xs = slices.Compact(xs)// 初始化线段树n := len(xs) - 1 // len(xs) 个横坐标有 len(xs)-1 个差值t := make(seg, 2<<bits.Len(uint(n-1)))t.build(xs, 1, 0, n-1)// 模拟扫描线从下往上移动slices.SortFunc(events, func(a, b event) int { return a.y - b.y })type pair struct{ area, sumLen int }records := make([]pair, m-1)totArea := 0for i, e := range events[:m-1] {l := sort.SearchInts(xs, e.lx)r := sort.SearchInts(xs, e.rx) - 1 // 注意 r 对应着 xs[r] 与 xs[r+1]=e.rx 的差值t.update(1, l, r, e.delta)         // 更新被 [e.lx, e.rx] 覆盖的次数sumLen := xs[len(xs)-1] - xs[0]    // 总的底边长度if t[1].minCover == 0 {            // 需要去掉没被矩形覆盖的长度sumLen -= t[1].minCoverLen}records[i] = pair{totArea, sumLen} // 记录关键数据totArea += sumLen * (events[i+1].y - e.y) // 新增面积 = 被至少一个矩形覆盖的底边长之和 * 矩形高度}// 二分找最后一个 < totArea / 2 的面积i := sort.Search(m-1, func(i int) bool { return records[i].area*2 >= totArea }) - 1return float64(events[i].y) + float64(totArea-records[i].area*2)/float64(records[i].sumLen*2)
}func main() {squares := [][]int{{0,0,1},{2,2,1}}result := separateSquares(squares)fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-import bisectclass SegTree:def __init__(self, xs):self.n = len(xs) - 1self.xs = xsself.size = 1while self.size < self.n:self.size *= 2self.min_cover = [0] * (2 * self.size)self.min_cover_len = [0] * (2 * self.size)self.todo = [0] * (2 * self.size)# 初始化叶子节点for i in range(self.n):self.min_cover_len[self.size + i] = xs[i+1] - xs[i]for i in range(self.n, self.size):self.min_cover_len[self.size + i] = 0for i in range(self.size - 1, 0, -1):self.maintain(i)def maintain(self, o):lo, ro = 2*o, 2*o+1mn = min(self.min_cover[lo], self.min_cover[ro])self.min_cover[o] = mnself.min_cover_len[o] = 0if self.min_cover[lo] == mn:self.min_cover_len[o] += self.min_cover_len[lo]if self.min_cover[ro] == mn:self.min_cover_len[o] += self.min_cover_len[ro]def do(self, o, v):self.min_cover[o] += vself.todo[o] += vdef spread(self, o):if self.todo[o] != 0:self.do(2*o, self.todo[o])self.do(2*o+1, self.todo[o])self.todo[o] = 0def update(self, l, r, v, o=1, segL=0, segR=None):if segR is None:segR = self.size - 1if l <= segL and segR <= r:self.do(o, v)returnself.spread(o)mid = (segL + segR) // 2if l <= mid:self.update(l, r, v, 2*o, segL, mid)if mid < r:self.update(l, r, v, 2*o+1, mid+1, segR)self.maintain(o)def separateSquares(squares):m = len(squares) * 2xs = []events = []for sq in squares:lx, y, l = sqrx = lx + lxs.extend([lx, rx])events.append((y, lx, rx, 1))events.append((y + l, lx, rx, -1))xs = sorted(set(xs))events.sort(key=lambda x: x[0])n = len(xs) - 1seg_tree = SegTree(xs)records = []tot_area = 0for i in range(len(events) - 1):y, lx, rx, delta = events[i]l = bisect.bisect_left(xs, lx)r = bisect.bisect_left(xs, rx) - 1seg_tree.update(l, r, delta)total_len = xs[-1] - xs[0]if seg_tree.min_cover[1] == 0:total_len -= seg_tree.min_cover_len[1]records.append((tot_area, total_len))next_y = events[i+1][0]tot_area += total_len * (next_y - y)# 二分查找target = tot_area / 2left, right = 0, len(records)while left < right:mid = (left + right) // 2if records[mid][0] * 2 >= tot_area:right = midelse:left = mid + 1i = left - 1if i < 0:return float(events[0][0])prev_area, total_len = records[i]prev_y = events[i][0]remaining_area = tot_area / 2 - prev_areareturn prev_y + remaining_area / total_lendef main():squares = [[0, 0, 1], [2, 2, 1]]result = separateSquares(squares)print(result)if __name__ == "__main__":main()