Constellation

题目传送门 更好看的题面 非常巧妙的凸包。 题目分析 这道题的本质就是将所有点划分为两个生成树，求可能的方案数。 part 1 求凸包的答案 我们可以考虑先求一个整体的凸包，如下图： 其中红色的点为星座 $A$，蓝色的点为星座 $B$，黑色的点不确定。 先考虑凸包上的点，对于凸包上的点，当存在红蓝红 ......

# G 星座 3 (Constellation 3) 总述：做法很多，一道练习各种套路的有价值的题。 对横坐标考虑一个区间 $[l, r]$，若该区间上建筑高度的最大值为 $x$，则该区间内 $> x$ 的星星数量不能超过 $1$ 个。 对建筑高度建出 **笛卡尔树**，于是每个节点对应一个区间以及 ......