题解：星空图的星座消除与最小化代价

问题分析

本题要求在一个 $N \times N$ 的网格中，通过删除星星（花费代价）来消除所有星座。星座定义为不包含白色像素且至少包含两颗星星的矩形区域。白色像素位于每列的下方 $A_i$ 行。

关键约束：

• 第 $i$ 列的白楼占据第 $1$ 到 $A_i$ 行
• 星星位于 $(X_j, Y_j)$，且保证 $Y_j > A_{X_j}$（星星在白楼上方）
• 需要选择一些星星删除，使得剩下的星星中不存在一个矩形区域不包含白色像素且包含至少两颗星星

关键观察

1. 星座的等价条件
   由于白楼是每列从底部开始的连续段，一个矩形区域不含白色像素 ⇔ 矩形的底边高度大于该区域内所有列的白楼高度。
   这意味着，对于任意两颗星星 $(X_1,Y_1)$ 和 $(X_2,Y_2)$，如果它们所在的矩形区域不包含白楼，那么这个矩形的底边高度必须大于 $\max(A_{X_1}, A_{X_2})$。

2. 转化为高度限制问题
   考虑两颗星星 $i$ 和 $j$。它们会形成一个星座当且仅当：

   • 它们所在的矩形区域内没有白楼
   • 即矩形的底边高度 > 该区域内每列的白楼高度 实际上，对于两颗星星，如果它们之间（在列区间上）的所有列的白楼高度都低于两颗星星中较低的 $y$ 坐标，则它们会构成星座。

3. 进一步简化
   可以将问题转化为：对于每一行高度 $h$，考虑所有 $Y_j = h$ 的星星。这些星星之间可能会形成星座。实际上，问题可以按行从高到低处理，维护每列当前允许的最高星星高度。

算法核心思路

数据结构设计

• 两个并查集：
  • fa1[x]：找到 $x$ 列左侧第一个可用的列（用于处理区间）
  • fa2[x]：找到 $x$ 列右侧第一个可用的列
• 树状数组：维护每列当前允许的最高星星高度的代价信息
• 邻接表存储：
  • head1[i]：存储白楼高度为 $i$ 的列（按行处理时使用）
  • head2[i]：存储位于第 $i$ 行的星星

处理流程

1. 按行从高到低处理
   对于当前行 $i$：

   • 处理所有位于这一行的星星
   • 对于每个星星 $(x, i, cost)$：
     • 查询当前列 $x$ 的可用代价 $t = \text{qry}(x)$
     • 如果 $t \ge cost$：直接删除该星星，花费 $cost$
     • 否则：需要调整区间代价，使得该列可用代价达到 $cost$
       • 增加左侧区间代价：$\text{upd}(fd1(fa1[x])+1, cost-t)$
       • 减少右侧区间代价：$\text{upd}(fd2(fa2[x]), t-cost)$
       • 总花费增加 $t$
   • 处理完星星后，处理白楼：
     • 对于所有白楼高度为 $i$ 的列，更新并查集，标记该列"被占用"

2. 代价调整的直观解释
   当一列的可用代价不足时，我们需要"借用"相邻列的代价。这实际上是在维护一个代价的"水位线"，使得每列的可用代价满足不形成星座的条件。

3. 最终答案
   累加所有删除操作的花费即为最小不自然度。

正确性证明

1. 无星座条件等价于单调性条件
   经过转化，问题等价于要求：对于任意两列 $i < j$，如果它们都有星星，那么这两颗星星的高度必须满足某种单调关系，以避免形成不含白楼的矩形。

2. 贪心策略的最优性
   按行从高到低处理，每次尽量保留高价值的星星（通过调整区间代价），这保证了最终方案的全局最优性。

3. 数据结构维护的正确性
   并查集维护了列的连通性，树状数组维护了区间代价和，两者结合高效处理了区间调整操作。

复杂度分析

• 时间复杂度：$O((N+M)\log N)$
  • 每个星星处理一次，每次需要 $O(\log N)$ 的查询和更新
  • 每列的白楼处理一次
• 空间复杂度：$O(N+M)$

对于 $N,M \le 2\times 10^5$ 的数据范围完全可行。

总结

本题是一道巧妙的数据结构与贪心结合的题目，主要考察：

1. 问题转化能力：将几何约束转化为序列上的单调性条件
2. 扫描线思想：按行从高到低处理，逐步构建合法状态
3. 数据结构运用：并查集维护区间连通性，树状数组维护区间和
4. 贪心决策：在满足约束的前提下最小化删除代价

算法的核心在于认识到：消除星座等价于维护每列星星高度的某种单调性，并通过动态调整区间代价来最小化总花费。通过从高到低扫描，并利用高效的数据结构，实现了对大规模数据的高效处理。

这种"扫描线+数据结构维护区间信息"的方法是解决此类二维约束问题的经典范式，在竞赛中具有广泛的应用。