P12564 [UTS 2024] Jobs

给定平面上 $n$ 个具有整数坐标的点的集合，每个点都有一个对应的权重。 我们可以通过一个坐标为 $(x, y)$ 的点将平面划分为四个象限：在 $x + 0.5$ 处画一条垂直线，在 $y + 0.5$ 处画一条水平线。定义一个象限的权重为该象限内所有点的权重之和。进一步地，这种划分的**不平衡度**定义为四个象限权重中最大差值。 对于每个满足 $1 \leq x < n$ 的整数 $x$，求在垂直线 $x$ 上进行划分时可能的最小不平衡度。

第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$)。 接下来的 $n$ 行，每行包含三个整数 $x_i$, $y_i$ 和 $w_i$ ($1 \leq x_i, y_i \leq n$, $1 \leq w_i \leq 10^9$) —— 分别表示第 $i$ 个点的横坐标、纵坐标和权重。

输出仅一行，包含 $n - 1$ 个整数，依次表示每个 $x$ 对应的最小不平衡度。

- （$7$ 分）：$1 \leq n \leq 200$； - （$17$ 分）：$1 \leq n \leq 5000$； - （$53$ 分）：$1 \leq n \leq 100\,000$； - （$23$ 分）：无额外限制。 翻译由 DeepSeek V3 完成